下面是几题关于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?
其他就不知道了
希望大家帮我看一下
我的答案有错也烦请指正
谢谢!