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?
