Re: why not just publish truth table?

On Aug 17, 9:53 am, "Pummelo" <pumm...@xxxxxxxxxxx> wrote:
"G. A. Edgar" <ed...@xxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

The algorithm "make the truth table" takes too long.

The problem "satisfiability" is NP complete.

If P <> NP, then every algorithm (not only that one) takes too long.

So I don't understand your point. You mean "because every algorithm consumes
too much time to be practical [which is certainly untrue, by the way]

certainly untrue? if P <> NP? what's your example algorithm for
satisfiability that does not consume too much time to be practical in
all instances?

than there are no reasons to bother with proof systems", right ?

I had trouble figuring out the direction of what you meant by this
with the context of the previous sentence. Without context, there are
very good reasons to bother with proof systems, namely, because
valuations (truth-table arguments) are inefficient.

Mitch

.

Relevant Pages

  • Re: sat to horn sat
    ... But maybe you want an algorithm that converts a sat instance you ... I'd just like to see an example of reduction from sat to horn sat. ... Tricky part is to define R so that it applies to all to sat instances preserving satisfiability. ... And surely there exists one that satisfies the requirement "X is satisfiable iff Ris satisfiable". ...
    (sci.math)
  • Re: sat to horn sat
    ... |>apoph wrote: ... |>>Is there an algorithm that turns sat instances into horn sat? ... R is not trivial in a sense that it first decides X and then outputs some fixed satisfiable or unsatisfiable horn sat instance accordingly to the satisfiability of X. ...
    (sci.math)
  • Satisfiability problem compiler
    ... If tomorrow somebody invented an algorithm to solve any satisfiability ... compiler which would (in polynomial time, or in some efficient way) convert ... Does anyone know of research into such a compiler? ...
    (comp.theory)
  • Re: why not just publish truth table?
    ... The problem "satisfiability" is NP complete. ... then every algorithm takes too long. ... REAL-TIME solvers) designed for particular tasks and performing well. ... with the context of the previous sentence. ...
    (sci.math)
  • Re: Javascript Best Practices Document v1.0
    ... unequivocally assert that a general algorithm must consider every ... (and 100% successful and accurate within its stated context) ... Real web sites are not radically re-designed at the ... > or even allow the end-users to alter the design. ...
    (comp.lang.javascript)