Showing that the decison version of an NP

Say you are given a combinatorial optimization problem A. Let us assume WLOG that the problem is the clique problem.

How can I show that if clique is NP-complete, then the decision version of clique is NP-complete, where the decision version is of course the following problem B: is there a clique of size equal to k?

I think I have the intuition in mind but not sure if it suffices as a proof:

Step I:

if I am given a set of vertices C of size k, I can verify in polynomial time that there is a clique of size k (assuming that the answer to B is yes ie there exists a clique of size k). Hence, B is in NP.

Step II: reduce A to B.

-Since A asks for the clique of maximum size, we can break the problem down into pieces, B1: is there a clique of size 1?, ..., BN: is there a clique of size N?

-If A is solvable, say there is a clique of size k*, then every Bk, k=1,...,N can be easily answered by comparing k to k*

-If all of the Bks are solvable, we can tell what is the maximum clique size.

I'm really not sure that this is a reduction although it's in polynomial time. Maybe because one problem is broken down into many problems. Moreover, I'm not sure I should be using the the word "all" above.

Thanks for the help! :)

---

A combinatorial optimization problem cannot be NP-complete. Only decision problems can be NP-complete (see, eg, http://en.wikipedia.org/wiki/NP-complete).

The Clique optimization problem (given a graph, find a maximal set of vertices that form a clique) is NP-hard, because its decision version (given a graph and ak, is there a clique of size >= k?) is NP-complete.

链接地址: http://www.djcxy.com/p/39998.html

上一篇: NP的复杂度测量

下一篇: 显示NP的Decison版本