Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

> Also, there are problems in NP that are neither in P, nor are they NP- or co-NP-complete.

Err, it seems to me you've got a very serious statement there. I think you mean “that are not known to be …”.



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...


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.


Yep. I should just stop posting today. :)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: