patternMinor
Why is Clique NP-complete while k-Clique is in P for all k?
Viewed 0 times
whywhileallcliquecompletefor
Problem
I just stumbled upon this question here Why is the clique problem NP-complete?
and I am confused by the given answer.
The question about about whether $k$-clique is NP-hard for a fixed $k$ and the answer is no. However, we know that clique in general is NP-hard. Also we know that $0 \leq k \leq n$ must hold (for a graph of size $n$).
What is wrong about the following reasoning:
Assume I have some algorithm $A_i$ that solves $i$-clique for some fixed $i$ in polynomial time.
Now given some general clique problem without a specific $k$ (these problems are supposedly NP-hard), I simply run $A_i$ for $i=1$ to $n$. Now since $n$ is poly and every $A_i$ runs in polynomial time $p_i$, the resulting algorithm also runs in polynomial time $\sum p_i$, but this cannot be the case, since clique is NP-hard.
What is wrong about my reasoning?
and I am confused by the given answer.
The question about about whether $k$-clique is NP-hard for a fixed $k$ and the answer is no. However, we know that clique in general is NP-hard. Also we know that $0 \leq k \leq n$ must hold (for a graph of size $n$).
What is wrong about the following reasoning:
Assume I have some algorithm $A_i$ that solves $i$-clique for some fixed $i$ in polynomial time.
Now given some general clique problem without a specific $k$ (these problems are supposedly NP-hard), I simply run $A_i$ for $i=1$ to $n$. Now since $n$ is poly and every $A_i$ runs in polynomial time $p_i$, the resulting algorithm also runs in polynomial time $\sum p_i$, but this cannot be the case, since clique is NP-hard.
What is wrong about my reasoning?
Solution
The polynomial depends on the parameter $k$. In particular, the algorithm that people have in mind runs in time $O(n^k)$ (better algorithms might exist, but I believe that we don't know a running time better than $O(n^{O(k)})$. The running time of your proposed algorithm is then big O of
$$
\sum_{k=1}^n n^k,
$$
which is no longer polynomial.
$$
\sum_{k=1}^n n^k,
$$
which is no longer polynomial.
Context
StackExchange Computer Science Q#63777, answer score: 6
Revisions (0)
No revisions yet.