Is the k-clique problem NP-complete?

Question

In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete:

Cliques have also been studied in computer science: finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.

But in this other Wikipedia article about the Clique problem in CS it says it is solving the problem for a fixed size k is a problem in P, it can be brute forced in polynomial time.

A brute force algorithm to test whether a graph G contains a k-vertex clique, and to find any such clique that it contains, is to examine each subgraph with at least k vertices and check to see whether it forms a clique. This algorithm takes time O(n^k k^2): there are O(n^k) subgraphs to check, each of which has O(k^2) edges whose presence in G needs to be checked. Thus, the problem may be solved in polynomial time whenever k is a fixed constant. When k is part of the input to the problem, however, the time is exponential.

Is there something I am missing here? Maybe a difference in the wording of the problem? And what does the last sentence mean, that "When k is part of the input to the problem, however, the time is exponential."? Why is there a difference when the k is part of the input to the problem?

My idea is that to find a clique of size k in a graph G, is that we first choose a subset of size k of nodes from G, and test wether they are all related to the other k nodes, which can be done in constant time. And repeat this until we have a clique of size k. The number of sets of k nodes we can choose from G is n! / k!*(n-k)!.

Answer 1

Just elaborating what @Lamine pointed out : When $k$ is part of the input, $k$ can be as large as $\frac{n}{2}$, in which case the number of potential clique sets are $\binom{n}{\frac{n}{2}}$ which is at least $\left( \frac{n}{\frac{n}{2}} \right)^{\frac{n}{2}}$. Hence your naive algorithm would take time $2^{\frac{n}{2}}$ which is clearly exponential in input length $|x|+|k|=n+\log n$. The parameterized version $G(n,k)$ where we are looking for $k$-cliques in an $n$-vertex graph captures the hardness of the problem in its most generalized form because $k$ is part of the input. Hence a poly-time algorithm for $G(n,k)$ would also imply a poly-time algorithm for any specific $k$.