Re: TAUTOLOGY and SAT
- From: cplxphil@xxxxxxxxx
- Date: Sun, 13 Jul 2008 11:14:43 -0700 (PDT)
On Jul 13, 12:44 pm, djime...@xxxxxxxxxxxxx (Daniel A. Jimenez) wrote:
In article <6c39b8ea-4d7f-4339-bdae-fccaf9454...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxp...@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 athttp://www.cs.uwaterloo.ca/~alopez-o/comp-faq/faq.html)
--
Daniel Jimenez djime...@xxxxxxxxxxxxx
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
Oh, okay, I see what you are saying. It does not qualify as a
polynomial time reduction unless the mapping actually yields an
instance of the "yes" version of the question. Thanks, I understand
what I previously misunderstood.
-Phil
.
- References:
- TAUTOLOGY and SAT
- From: cplxphil
- Re: TAUTOLOGY and SAT
- From: Daniel A. Jimenez
- TAUTOLOGY and SAT
- Prev by Date: Re: TAUTOLOGY and SAT
- Next by Date: Re: NP problem and co-NP problem
- Previous by thread: Re: TAUTOLOGY and SAT
- Index(es):
Relevant Pages
|
|
