Proving that P <= NP
- by Gail
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?