TAUTOLOGY and SAT


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
.

Relevant Pages

  • Re: How much intelligence?
    ... If a negation results in a regression, what about the opposite of the ... There is no contradiction self or otherwise in A not A. ... Regression and tautology seem contradicting terms. ...
    (comp.ai.philosophy)
  • Re: How much intelligence?
    ... If a negation results in a regression, what about the opposite of the ... There is no contradiction self or otherwise in A not A. ... Regression and tautology seem contradicting terms. ...
    (comp.ai.philosophy)
  • Re: An UnSat Solver
    ... DNF expression that must be a tautology if the 3SAT instance is ... the negation of the instance. ... The variable order chosen will also affect the size of the certificate. ... that will always result in an exponential size BDD diagram. ...
    (comp.theory)
  • Re: mathematical language
    ... Your example corresponds to what I think is a tautology. ... >statement which excludes no logical possibility" took me a while to parse, ... >level of negation and still maintain, ... useless and anything which is useless is a tautology and circular ...
    (sci.math)
  • Re: mathematical language
    ... Your example corresponds to what I think is a tautology. ... >statement which excludes no logical possibility" took me a while to parse, ... >level of negation and still maintain, ... useless and anything which is useless is a tautology and circular ...
    (comp.theory)