¿El problema k-clique NP-completo?

En este artículo de Wikipedia sobre el problema de la camarilla en la teoría de grafos , establece al principio que el problema de encontrar una camarilla de tamaño K, en un gráfico G es NP-completo:

Las camarillas también se han estudiado en ciencias de la computación: descubrir si hay una camarilla de un tamaño determinado en un gráfico (el problema de la camarilla) es NP completo, pero a pesar de este resultado de dureza, se han estudiado muchos algoritmos para encontrar camarillas.

Pero en este otro artículo de Wikipedia sobre el problema de Clique en CS dice que está resolviendo el problema para un tamaño fijo k es un problema en P, puede ser forzado en tiempo polinómico.

Un algoritmo de fuerza bruta para probar si un gráfico G contiene una camarilla k-vértice, y para encontrar cualquier camarilla que contenga, es examinar cada subgrafía con al menos k vértices y verificar si forma una camarilla. Este algoritmo requiere tiempo O (n ^ kk ^ 2): hay O (n ^ k) subgráficos para verificar, cada uno de los cuales tiene bordes O (k ^ 2) cuya presencia en G necesita ser verificada. Por lo tanto, el problema puede resolverse en tiempo polinómico siempre que k sea una constante fija. Cuando k es parte de la entrada al problema, sin embargo, el tiempo es exponencial.

¿Hay algo que me falta aquí? Tal vez una diferencia en la redacción del problema? ¿Y qué significa la última oración, que "Cuando k es parte de la entrada al problema, sin embargo, el tiempo es exponencial"? ¿Por qué hay una diferencia cuando la k es parte de la entrada al problema?

Mi idea es que para encontrar una camarilla de tamaño k en un gráfico G, es que primero elegimos un subconjunto de tamaño k de nodos de G, y probamos si todos están relacionados con los otros k nodos, lo que se puede hacer en constante hora. Y repita esto hasta que tengamos una camarilla de tamaño k. ¡El número de conjuntos de k nodos que podemos elegir entre G es n! / k! * (nk) !.

Simplemente elaborando lo que @Lamine señaló: cuando es parte de la entrada, puede ser tan grande como , en cuyo caso el número de posibles conjuntos de camarillas es que es al menos . Por lo tanto, su algoritmo ingenuo tomaría tiempo que es claramente exponencial en la longitud de entrada . La versión parametrizada donde buscamos cliques en un gráfico vértice captura la dureza del problema en su forma más generalizada porque$k$$k$$\frac{n}{2}$$\binom{n}{\frac{n}{2}}$$\left( \frac{n}{\frac{n}{2}} \right)^{\frac{n}{2}}$$2^{\frac{n}{2}}$$|x|+|k|=n+\log n$$G(n,k)$$k$$n$$k$Es parte de la entrada. Por lo tanto, un algoritmo de poli-tiempo para también implicaría un algoritmo de poli-tiempo para cualquier específico .$G(n,k)$$k$