下面是幾題關於NP的是非題,T,F或是unknown
(a)If a problem is in P, it must also be in NP.
(b)If a problem is in NP, it must also be in P.
(c)If a problem is NP-complete, it must also be in NP.
(d)If a problem is NP-complete, it must not be in P.
(e)If a problem is not in P, it must be NP-complete.
(f)If P=NP, then the SAT problem is also in P.
(g)If P ≠ NP, then there is no polynomial-time reduction from TSP (the
traveling salesman problem) to a shortest path problem solvable by
Dijkstra's algorithm.
(h)The clique problem can be reduced to the 3SAT problem in polynomial time.
(i)Both 0/1 and fractional knapsack problems are in P.
(j)It must be the case that either both SAT and Hamiltonian cycle are in P,
or both are not in P.
我自己的想法前六題是 T, unknow, T, unknow, F, T
(h)的話證明流程通常是3SAT reduce到 clique 所以應該是F?
(i)應該是F?
其他就不知道了
希望大家幫我看一下
我的答案有錯也煩請指正
謝謝!