das Problem, für einen ungerichteten Graphen G = (V, E) und eine Zahl k zu entscheiden, ob G eine Clique mit k Knoten enthält.

Das Cliquenproblem gehört zu den ersten Problemen, für die nachgewiesen wurde, daß es NP-vollständig ist. Bei der Optimierungsvariante (Optimierungsproblem) besteht das Ziel darin, die Größe der größten Clique zu berechnen. Der beste bekannte polynomielle Approximationsalgorithmus (approximativer Algorithmus) erreicht eine Güte von n/ log n. Mit Hilfe der von PCP-Theorie konnte gezeigt werden, daß es ein NP-schweres Problem ist, gute Approximationen zu berechnen.