Re: co-NP in P?
- From: Doug Elrod <dre1@xxxxxxxxxxx>
- Date: Mon, 22 Aug 2005 16:00:19 -0400
In article <e4ydndKeFY1ZgpfeRVn-hw@xxxxxxxxxxx>,
"Russell Easterly" <logiclab@xxxxxxxxxxx> wrote:
> What would be the ramifications of proving that UNSAT is in P?
If UNSAT is in P, then there is a P-time deterministic Turing machine
accepting UNSAT. Negate the output of this Turing machine and you
have a P-time acceptor for SAT. So P=NP, with all that entails ;-).
-Doug Elrod (dre1@xxxxxxxxxxx)
.
- Prev by Date: Re: Can any one have solution???
- Next by Date: Re: Solving linear system of equalities AND disequalities
- Previous by thread: Can any one have solution???
- Next by thread: An MSSP-Like Problem
- Index(es):
