If a problem can be verified in polynomial time, then it's in the NP class. Another definition: if the language of a problem can be accepted by some polynomial-bounded non-deterministic Turing machine. If the language can be accepted by some polynomial-bounded deterministic Turing machine, then it's in P. Thus, P \in NP.
Apparently finding the solution itself can be hard, although the verification is often trivial.
Reducibility: If A reduces to B in polynomial time. B can be harder? At least as hard.
like SAT <=p 3SAT. 3SAT is harder. If we can solve 3SAT, we solve all SAT problems.
If all problems in NP can be reduced to A, then A is NP-hard. A doesn't have to a NP problem. So there are some NP-hard problems that are not in NP? If we solve a NP-hard problem, we solve all NP problems, including those NP-complete ones.
Seems not all NP-hard problems are equally hard. Those are not in NP are harder?
If we can show a problem is in NP, and it's NP-hard, then it's a NP-complete problem. seems NP-Complete are the hardest problems in NP? And also are all NP-complete problems equivalent?
So next mission for scientist: find one NP-complete problem and solve it!
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment