# If A is reducible to B and B is reducible to A, and A is NPC, is B also NPC?

I was thinking about the max-clique problem and the k-independent set problem. You can show that k-independent set is reducible to max-clique easily and you can show that max-clique is reducible to k-independent set (with a simple for loop). And k-independent set is NPC, so wouldn't that mean max-clique is also NPC, but it's not because we can't create a verifier, so I'm terribly confused. What wrong assumption am I making?

• The decision version of max-clique is actually k-clique, which is NP-complete. – Albert Hendriks May 31 '18 at 5:50
• @AlbertHendriks So max-clique typically asks for a set of vertices, not a yes or no answer? – notorious May 31 '18 at 5:52
• Yes, or the size of the clique, as the current answer indicates. Perhaps there's another decision version that says "Does the max clique contain a specific vertex X?" but then it's not reducible to k-independent set. – Albert Hendriks May 31 '18 at 5:55
• @notorious The answer I gave before was downright incorrect; it's been corrected now. Sorry about that! – Draconis May 31 '18 at 19:07

One of them is the Clique Decision Problem: given an undirected graph $G$ and a number $k$, does $G$ contain a clique with at least $k$ vertices? This is one of Karp's 21 Problems, the original list that made NP-completeness famous. The proof involved reducing to it from the Boolean Satisfiability Problem, the very first original NP-complete problem. And a verifier for this is easy to make: check whether the set given as a solution actually does contain $k$ or more vertices, and is actually a clique.
The other is the Maximum Clique Size Problem: given an undirected graph $G$, what is the size of the largest clique in $G$? This can be shown to be NP-hard by reduction from the Clique Decision Problem, by simply comparing the size of the largest clique with $k$. And as you mentioned, it can apparently be shown to be in NP by reduction to the Clique Decision Problem: for every integer from the number of vertices down to 1, check if there's a clique of that size, and if so return that number.