Informatik

Gegeben ein Graph $G$ und eine Zahl $k$: Gibt es eine Clique der Größe $k$?

Eine Clique ist eine Knotenmenge, in der jedes Knotenpaar durch eine Kante verbunden ist. Das Entscheidungsproblem ist NP-vollständig.