# Pseudopolynomials and $NP$ problems like $CLIQUE$

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?

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).