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开发者_Go百科 know how to state that P <= NP. It's just intuitive. How would you prove that P <= NP?

---

Each problem in NP is solved by a nondeterministic Turing machine [in polynomial time]. (by definition*)

Each problem in P is solved by a deterministic Turing machine [in polynomial time]. (by definition)

Each deterministic Turing machine is a nondeterministic Turing machine as well. (obviously)

Hence each problem in P is solved by a nondeterministic Turing machine [in polynomial time].

Hence each problem in P is a problem in NP. Hence P ⊆ NP.

---

*Let's read Wikipedia article on NP:

In an equivalent formal definition, NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine.

There's no need to introduce this stuff about polynomial verification into such a simple reasoning.

---

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.

---

A nondeterministic computer can simply not invoke its nondeterminism and act like a deterministic one, thus it can run P problems in polynomial time. That's the best answer I can think of.

---

A non-deterministic computer that solves a (NP) problem in polynomial time would also solve a P problem in polynomial time.

If we consider the imaginary approach of a Turing Machine that can take several paths at a decision to solve the NP problem in polynomial time, this behaviour must be enough to solve the P problem in P Time. Deterministic Turing machines are a case of simple (real) non-deterministic machines.

---

ach problem in NP is solved by a nondeterministic Turing machine [in polynomial time]. (by definition*)

Each problem in P is solved by a deterministic Turing machine [in polynomial time]. (by definition)

Each deterministic Turing machine is a nondeterministic Turing machine as well. (obviously)

Hence each problem in P is solved by a nondeterministic Turing machine [in polynomial time].

Hence each problem in P is a problem in NP. Hence P ⊆ NP.