Re: TAUTOLOGY and SAT

In article <6c39b8ea-4d7f-4339-bdae-fccaf945444b@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:

Hi, I'm relocating this from the other thread I posted this in...I
didn't intend to change the focus from the original poster's question,
I apologize.

But here is my question...is it true that TAUTOLOGY and SAT are
polynomial time equivalent? It seems to me that they must be, because
given a propositional formula, that formula is satisfiable if its
negation is not a tautology, and a formula is a tautology if its
negation is not satisfiable.

Am I correct in this? I read somewhere that this was not true, but I
do not see why not. (I don't know if the source was reliable or
not.) This seems perfectly logical to me, and it's a many-one
reduction.

-Phil

Look at the question in terms of membership in languages, where terms like
"polynomial time equivalent" make sense. Being able to decide whether
strings are in a certain language doesn't necessarily make it easy to
decide whether strings are in the complement of that language. "[A]
formula is satisfiable if its negation is not a tautology." That's true,
but "not a tautology" is a different language than TAUTOLOGY. TAUTOLOGY is
in co-NP where "not a tautology" is in NP.

Still confused? Recall that a language said to be in NP if there
exists a polynomial proof system for the language, i.e., there exists a
polynomial-sized certificate that can be used by a polynomial time algorithm
to verify that a string is a member of the language. Now think about your
question this way: what would be a polynomial certificate showing that a
string is in SAT? A satisfying assignment. What would be a polynomial
certificate for "not a tautology?" An assignment that fails to satisfy
the formula. Thus SAT and "not a tautology" are both in NP. Now what
would be a polynomial certificate for TAUTOLOGY? Or for "not satisfiable?"
Think about it a little while, and if you find the answer for either of
those let me know and I'll be happy to write it up with you :-). (That is,
giving an answer for either of those would be a proof that co-NP=NP.)

Another way to answer your question would be to say those two problems
are equivalent in the sense that a deterministic algorithm for deciding
one could easily be adapted to decide the other. However, non-determinism
(in the sense of NP) doesn't work that way, e.g., the fact that a polynomial
proof system for SAT exists doesn't mean that a polynomial proof system for
"not satisfiable" exists.

(For more on the polynomial certificate formulation of NP, see the
comp.theory FAQ at http://www.cs.uwaterloo.ca/~alopez-o/comp-faq/faq.html )
--
Daniel Jimenez djimenez@xxxxxxxxxxxxx
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
.

Relevant Pages

  • Re: TAUTOLOGY and SAT
    ... negation is not a tautology, and a formula is a tautology if its ... "polynomial time equivalent" make sense. ... decide whether strings are in the complement of that language. ... A satisfying assignment. ...
    (comp.theory)
  • Re: Godels comments about the "true reason" for incompleteness
    ... where P and Q are arbitrary) into the language ... yield that every first order theory proves EVERY tautology in the ... INSTANCES of a schema have truth values, ...
    (sci.logic)
  • Re: Godels comments about the "true reason" for incompleteness
    ... this single sentence, where P and Q are arbitrary) into the language ... yield that every first order theory proves EVERY tautology in the ... INSTANCES of a schema have truth values, ...
    (sci.logic)
  • Re: Tautologies Then and Now
    ... >> sentence of a given language that is true in all interpretations of the ... So, alternatively, a tautology is a logical truth of ... >> Chris Menzel ...
    (sci.logic)