views:

247

answers:

4

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?

+1  A: 

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.

Joey Adams
+8  A: 

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.

Jefromi
A: 

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.

Marcos Carceles
+6  A: 
Pavel Shved
+1, though I'm not sure if one definition is really that much simpler than the other - one could also say there's no need to introduce stuff about determinism into reasoning as simple as polynomial time solving/verification.
Jefromi
@Jefromi, for *this* particular question it is simplier. And for *some* other questions, perhaps, it's simplier as well. One should not forget that there are several equivalent definition.
Pavel Shved
The equivalence of the definitions was the main thing I was trying to emphasize, along with the fact that "simpler" is a bit subjective.
Jefromi