Pseudopolynomials and $NP$ problems like $CLIQUE$

Question

Having encountered the concept of "pseudopolynomials", my understanding is that we have to be careful when the input to a problem is a number, that the complexity of the solution should be polynomial in the length of its representation and not its value; that is, if we want a solution polynomial in the size of the input.

For example, in his book "Computational Complexity", Papadimitriou says about the dynamic programming $KNAPSACK$ solution in time $O(nW)$ (where $n$ is the number of items and $W$ the weight limit):

This is not a polynomial algorithm because its time bound $nW$ is not a polynomial function of the input: The length of the input is something like $n \log W$.

But doesn't that apply to any problem whose input involves an integer? For example, I find it hard to see how the nondeterministic solution of $CLIQUE$ takes polynomial time.

Using nondeterministic-choice pseudocode, the classic solution seems to be:

solve_clique(G=(V, E), K):
    S := {}
    for i = 1..K
        S := S u choice(V)

   return check_clique(G, K, S)

But isn't the loop from 1 to $K$ exponential in the size of the input (of size $\log K$?)?

Even moving away from nondeterminism and thinking about the certificate-definition of $NP$ leaves me confused: the certificate is a clique of size $K$, so to go through all the nodes would require time exponential in $\log K$.

Is the key idea here that the clique size cannot exceed $|V|$? So $K \le |V|$; and since the input already contains the graph (say, represented in $O(|V|^2)$ by an adjacency matrix, then the clique is actually exponential in $\log |V|$ so polynomial in the input size?

Answer 1

The number $K$ of iterations of the loop is exponential in the size of the representation of $K$ (which is $\log K$) but it is polynomial in the size of the input of the problem. The input of the problem is not just the integer $K$ but both the graph $G$ and $K$. The size of the representation of $G$ is $\Omega(|V|)$ and $K \le |V|$.

The same reasoning applies to the certificate: the length of the certificate needs to be polynomial in the size of the input instance, and the certificate checker also needs to run in polynomial-time w.r.t. the input instance (and hence also w.r.t. the certificate). If you find a clique of size $K$ you can clearly encode this solution in a certificate of size $O(K) \subseteq O(N)$ (for example by listing the "names" of the nodes of the clique).