I am reading a proof on CLIQUE is NP-Complete. The first step is of course to show that CLIQUE is NP.
c is the clique certificate
V = “On input $\langle\langle G, k\rangle, c\rangle$:
- Test whether c is a set of k different nodes in G.
- Test whether G contains all edges connecting nodes in c.
- If both tests pass, accept; otherwise, reject.”
c just some arbitrary chosen set of k nodes? How would complexity analysis for 1 and 2 give polynomial time?