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?


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.