Re: NP vs co-NP

On Jul 13, 9:33 am, cplxp...@xxxxxxxxx wrote:
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


Wait...I think I'm wrong. But I don't know why. (I have a tendency
to make mistakes.) What the error in my logic is I don't know,
however.

-Phil

.