Proving that P <= NP

Posted by Gail on Stack Overflow See other posts from Stack Overflow or by Gail
Published on 2010-04-14T17:18:50Z Indexed on 2010/04/14 17:23 UTC
Read the original article Hit count: 373

Filed under:

As most people know, P = NP is unproven and seems unlikely to be true. The proof would prove that P <= NP and NP <= P. Only one of those is hard, though.

P <= NP is almost by definition true. In fact, that's the only way that I know how to state that P <= NP. It's just intuitive. How would you prove that P <= NP?

© Stack Overflow or respective owner

Related posts about computer-science