computer-sciencenp

Proving that P <= NP


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?


Solution

  • I think you've essentially answered your own question in the comments: a problem which satisfies the definition of P also satisfies the definition of NP.

    To quote wikipedia:

    All problems in P [are in NP] (For, given a certificate for a problem in P, we can ignore the certificate and just solve the problem in polynomial time. Alternatively, note that a deterministic Turing machine is also trivially a non-deterministic Turing machine that just happens to not use any non-determinism.)

    The certificate it refers to is the polynomial-time verification of solution; as you say, you can solve a problem in P in polynomial time and you will therefore have a solution which has been verified in polynomial time and is therefore in NP.

    Joey Adams' answer is the second explanation, in terms of solvability by (non)deterministic Turing machines. See the wikipedia article for a bit more explanation of that definition of NP.

    I think what you should note here is that the fact that the proof is trivially simple doesn't mean it's not a proof. "By definition" is a perfectly valid logical step.