Re: NP vs co-NP

On Jul 13, 9:03 am, "Fra" <fra.cristi...@xxxxxxxxx> wrote:
<cplxp...@xxxxxxxxx> has written news:fe229ad0-67e6-409a-97d0-

Yes, SAT is reducible to TAUTOLOGY;

Can you cite some references about this?

I knew only what is written here (Claim 4):

http://zoo.cs.yale.edu/classes/cs468/hw1.pdf

I realized that I was not answering his question, I had misread what
was written. That is why I deleted what I wrote.

However, I do believe that SAT is reducible to TAUT, although I'm not
an expert on this sort of thing.

SAT should be polynomial time equivalent to TAUT because all you need
to do to determine if a formula is satisfiable is to see if its
complement is a tautology. If it is, then the formula is
unsatisfiable. If it is not, the formula is not satisfiable.
Likewise, you can determine if a formula is a tautology by checking to
see if its complement is satisfiable. If it is satisfiable, then the
formula is not a tautology.

-Phil
.

Relevant Pages

  • Re: NP vs co-NP
    ... I realized that I was not answering his question, I had misread what ... However, I do believe that SAT is reducible to TAUT, although I'm not ... you can determine if a formula is a tautology by checking to ... see if its complement is satisfiable. ...
    (comp.theory)
  • Re: Revised Tautology FAQ - Thread-2
    ... should be in the FAQ tautology page relating to "SoF as a tautology." ... title of the fourth chapter from "NATURAL SELECTION" to "NATURAL ... OR THE SURVIVAL OF THE FITTEST." ... I was trying to find out just who came up with this tautology argument originally, and stumbled across these references that discuss it directly but don't explain where it came from. ...
    (talk.origins)