2. (55%) P and NP (2000) Give the definition of PNP, NP-hard, and NP-completenes
ID: 3908733 • Letter: 2
Question
2. (55%) P and NP (2000) Give the definition of PNP, NP-hard, and NP-completeness (5%) is the Euler path problem in NP? No explanation required. (5%) Is the Hamiltonian path problem in NP? No explanation required. (596) Suppose problem P. can be reduced to problem P, and we know P2 is NP-hard. Can we say P1 must be also NP-hard? Briefly explain your answer. (596) If problem A is NP-hard and problem B is NP-complete, can we say problem B must be reducible to problem A? (5%) If any NP-hard problem is solved in polynomial time, can we say that all problems in NP are now solvable in polynomial time? A. B. C. D. E. F. G. (1096) Prove that the Traveling Salesman Problem is NP-hard via reduction from Hamiltonian cycle problem. Illustrate your reduction using the following graph.Explanation / Answer
A.
P : All class of problems that can be solved in polynomial time by deterministic turing machine comes under P.
NP : There are problems that cannot be solved by deterministic turing machine in polynomial time. To solve such problems in polynomial time, non-deterministic turing machine is required. Such problems comes under NP.
NP-Hard : A problem Q is NP-Hard if every problem in NP can be reduced to Q in polynomial time
NP-Complete : A problem Q is NP-complete if it is NP and every problem in NP can be reduced to Q in polynomial time i.e. NP-Complete problem is both NP and NP-Hard.
B.
Euler path problem can be solved in polynomial time i.e. it is in class P problem.
P is a subset of class NP. Therefore, euler path problem is NP
C.
Hamilton path problem is NP-Complete and every NP-complete problem is NP . Hamilton path is NP
D.
By the definition of NP-Hard , a problem Q is NP-Hard if every problem in NP can be reduced to it.
Therefore, if P1 can be reduced to P2 and P2 is NP-Hard then it is not necessary for P1 to be NP-Hard.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.