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 i.e. 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! :)
