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.
精彩评论