Re:The polynomial algorithm for 3-SAT problem (or P=NP)
by JoeCamel on Thursday January 20, 2011 @05:17AM
(#2123206)
No, there actually are problems in "NP-intermediate" class (if P!=NP) although they are artificial. :) And, of course you are right, for many other problems researchers suspect they might be in NPI. See http://cstheory.stackexchange.com/questions/79/problems-betw...
Re:The polynomial algorithm for 3-SAT problem (or P=NP)
by lmkg on Thursday January 20, 2011 @12:31PM
(#2124387)
It's been proven that if P != NP, then there are problems in NP, which are neither in P nor NP-complete. We don't know what those problems are, because identifying such a problem would prove P != NP. There are candidates, such as factoring, for which there are neither polynomial algorithms nor proofs of NP-completeness, but definitively identifying them is at least as hard as proving P != NP, and possibly harder.
Err, it seems to me you've got a very serious statement there. I think you mean “that are not known to be …”.