Prev: I challenge any of you to a polynomial time parsing debate on this thread
Next: Globally defined solutions.
From: Tim Little on 24 Jun 2010 23:15
On 2010-06-24, Freed <kristian.freed(a)gmail.com> wrote:
> However, the number of literals I'll be working with will be so
> large that this naive approach is not feasible.

If the naive approach is infeasible, then there exist statements for
which *no* approach is feasible. For example, suppose you have the
information "fewer than 25 of the variables are false" with a set of
50 variables.

Then every disjunction of 25 variables is true, and they are all
minimal. There are approximately 1.3x10^12 such disjunctions. This
is more than 10% of the size of all possible truth-assignments so if
one is infeasibly large then likely so is the other.


So if there exists any feasible algorithm at all, it has to depend
upon special (as yet unstated) properties of the expected input.


- Tim
 | 
Pages: 1
Prev: I challenge any of you to a polynomial time parsing debate on this thread
Next: Globally defined solutions.