Editing Clique problem (section)

===NP-completeness===
[[File:Sat reduced to Clique from Sipser.svg|thumb|The 3-CNF Satisfiability instance (x ∨ x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y) reduced to Clique. The green vertices form a 3-clique and correspond to a satisfying assignment.<ref>Adapted from {{harvtxt|Sipser|1996}}</ref>]]
The clique decision problem is [[NP-complete]]. It was one of [[Karp's 21 NP-complete problems|Richard Karp's original 21 problems]] shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems".{{sfnp|Karp|1972}}  This problem was also mentioned in [[Stephen Cook]]'s paper introducing the theory of NP-complete problems.{{sfnp|Cook|1971}} Because of the hardness of the decision problem, the problem of finding a maximum clique is also NP-hard. If one could solve it, one could also solve the decision problem, by comparing the size of the maximum clique to the size parameter given as input in the decision problem.

Karp's NP-completeness proof is a [[many-one reduction]] from the [[Boolean satisfiability problem]]. It describes how to translate Boolean formulas in [[conjunctive normal form]] (CNF) into equivalent instances of the maximum clique problem.<ref>{{harvtxt|Cook|1971}} gives essentially the same reduction, from [[3-SAT]] instead of Satisfiability, to show that [[subgraph isomorphism]] is NP-complete.</ref> Satisfiability, in turn, was proved NP-complete in the [[Cook–Levin theorem]]. From a given CNF formula, Karp forms a graph that has a vertex for every pair {{math|(''v'',''c'')}}, where {{mvar|v}} is a variable or its negation and {{mvar|c}} is a clause in the formula that contains {{mvar|v}}. Two of these vertices are connected by an edge if they represent compatible variable assignments for different clauses. That is, there is an edge from {{math|(''v'',''c'')}} to {{math|(''u'',''d'')}} whenever {{math|''c''&nbsp;≠&nbsp;''d''}} and {{mvar|u}} and {{mvar|v}} are not each other's negations. If {{mvar|k}} denotes the number of clauses in the CNF formula, then the {{mvar|k}}-vertex cliques in this graph represent consistent ways of assigning [[truth values]] to some of its variables in order to satisfy the formula. Therefore, the formula is satisfiable if and only if a {{mvar|k}}-vertex clique exists.{{sfnp|Karp|1972}}

Some NP-complete problems (such as the [[travelling salesman problem]] in [[planar graph]]s) may be solved in time that is exponential in a sublinear function of the input size parameter {{mvar|n}}, significantly faster than a brute-force search.<ref>{{harvtxt|Lipton|Tarjan|1980}}.</ref> However, it is unlikely that such a subexponential time bound is possible for the clique problem in arbitrary graphs, as it would imply similarly subexponential bounds for many other standard NP-complete problems.{{sfnp|Impagliazzo|Paturi|Zane|2001}}