# Why finding out an independent set of size k is in NP-C and not in P? [duplicate]

I came across a statement in my book which claims that the problem P1 in NP-C and P2 is P.

P1: Given graph G(V, E), find out whether there exists an independent set of size k in the graph, where k is any positive integer.

P2: Given graph G(V, E), find out whether there exists an independent set of size 5 in the graph.

I cant get my head around this! I believe both should be in polynomial order.

Reason: $$\binom{n}{5}=O(n^5)$$ and so should $$\binom{n}{k}=O(n^k)$$.

Can anyone please explain whether I am right? or if not, what am I doing wrong?

Thanks in advance!

• $O(n^k)$ isn't polynomial in $k$... – John Dvorak Jan 22 '19 at 3:47
• @Juho That question is related, but not a duplicate, imo. The basic error is the same, but the approaches in the questions are different. (as well as the problems, although these are also very related. – Discrete lizard Jan 22 '19 at 8:04
• Perhaps it would be clearer to say that for P1, you are given the graph G and any integer k as input. – Discrete lizard Jan 22 '19 at 8:05
• Hi @Discretelizard, I have made the changes. I hope it's better now – Abhilash Mishra Jan 22 '19 at 9:09
• Well, I meant that it may be clearer for you to note that k is part of the input. Try to think about it – Discrete lizard Jan 22 '19 at 15:37