Menu
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?
424
One way to prove that P = NP is to show that the complexity measure TM (n) for some NP problem, like the 3-CNF-SAT problem, cannot be reduced to a polynomial time. We will show that the 3-CNF-SAT problem behaves as a common safe problem and that its complexity is time dependent.
If P equals NP, every NP problem would contain a hidden shortcut, allowing computers to quickly find perfect solutions to them. But if P does not equal NP, then no such shortcuts exist, and computers' problem-solving powers will remain fundamentally and permanently limited.
The statement P=NP means that if a problem takes polynomial time on a non-deterministic TM, then one can build a deterministic TM which would solve the same problem also in polynomial time. So far nobody has been able to show that it can be done, but nobody has been able to prove that it cannot be done, either.
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
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.
151
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
