单选题：Assume P≠NP, please identify the false statement.
Assume P≠NP, please identify the false statement. @[C](2)
A. There cannot exist a ρ-approximation algorithm for bin packing problem for any $$\rho<3/2$$.
B. In the minimum-degree spanning problem, we are given a graph G=(V, E) and wish to find a spanning tree T of G so as to minimize the maximum degree of nodes in T. Then it is NP-complete to decide whether or not a given graph has minimum-degree spanning tree of maximum degree two.
C. In the minimum-degree spanning problem, we are given a graph G=(V, E) and wish to find a spanning tree T of G so as to minimize the maximum degree of nodes in T. Then there exists an algorithm with approximation ratio less than 3/2.
D. In the knapsack problem, for any given real number $$\epsilon>0$$, there exists an algorithm with approximation ratio less than $$1+\epsilon$$.
A.There cannot exist a ρ-approximation algorithm for bin packing problem for any $$\rho<3/2$$.
B.In the minimum-degree spanning problem, we are given a graph G=(V, E) and wish to find a spanning tree T of G so as to minimize the maximum degree of nodes in T. Then it is NP-complete to decide whether or not a given graph has minimum-degree spanning tree of maximum degree two.
C.In the minimum-degree spanning problem, we are given a graph G=(V, E) and wish to find a spanning tree T of G so as to minimize the maximum degree of nodes in T. Then there exists an algorithm with approximation ratio less than 3/2.
D.In the knapsack problem, for any given real number $$\epsilon>0$$, there exists an algorithm with approximation ratio less than $$1+\epsilon$$.
答案：C
A. There cannot exist a ρ-approximation algorithm for bin packing problem for any $$\rho<3/2$$.
B. In the minimum-degree spanning problem, we are given a graph G=(V, E) and wish to find a spanning tree T of G so as to minimize the maximum degree of nodes in T. Then it is NP-complete to decide whether or not a given graph has minimum-degree spanning tree of maximum degree two.
C. In the minimum-degree spanning problem, we are given a graph G=(V, E) and wish to find a spanning tree T of G so as to minimize the maximum degree of nodes in T. Then there exists an algorithm with approximation ratio less than 3/2.
D. In the knapsack problem, for any given real number $$\epsilon>0$$, there exists an algorithm with approximation ratio less than $$1+\epsilon$$.
A.There cannot exist a ρ-approximation algorithm for bin packing problem for any $$\rho<3/2$$.
B.In the minimum-degree spanning problem, we are given a graph G=(V, E) and wish to find a spanning tree T of G so as to minimize the maximum degree of nodes in T. Then it is NP-complete to decide whether or not a given graph has minimum-degree spanning tree of maximum degree two.
C.In the minimum-degree spanning problem, we are given a graph G=(V, E) and wish to find a spanning tree T of G so as to minimize the maximum degree of nodes in T. Then there exists an algorithm with approximation ratio less than 3/2.
D.In the knapsack problem, for any given real number $$\epsilon>0$$, there exists an algorithm with approximation ratio less than $$1+\epsilon$$.
答案：C