I’m a slight disagreement with my professor over whether or not a certain reduction is possible. He asked us to reduce the problem of 3-Coloring to the problem of 3-Clique. The problem is that I’m fairly confident that 3-Coloring is NP-Complete, while 3-Clique is P. Correct me if I’m wrong (which is very likely), but for any k-clique where the k is fixed, is $ V^k$ , meaning the 3-clique is $ V^3$ , right? I asked my professor about this and his response was:
“3-clique is definitely not in P. You (apparently) have to examine all thrices of vertices to settle the matter.”
And I still don’t understand how this is not a $ V^3$ operation.
If I figured out a way to reduce 3-coloring to 3-clique wouldn’t I be millionaire?