Editing Clique problem (section)

===Decision tree complexity===

[[File:Decision tree for 3-clique no arrowheads.svg|thumb|A simple decision tree to detect the presence of a 3-clique in a 4-vertex graph. It uses up to 6 questions of the form "Does the red edge exist?", matching the optimal bound ''n''(''n''&nbsp;&minus;&nbsp;1)/2.]]
The (deterministic) [[decision tree complexity]] of determining a [[graph property]] is the number of questions of the form "Is there an edge between vertex {{mvar|u}} and vertex {{mvar|v}}?" that have to be answered in the worst case to determine whether a graph has a particular property. That is, it is the minimum height of a Boolean [[Decision tree model|decision tree]] for the problem. There are {{math|''n''(''n''&nbsp;&minus;&nbsp;1)/2}} possible questions to be asked. Therefore, any graph property can be determined with at most {{math|''n''(''n''&nbsp;&minus;&nbsp;1)/2}} questions. It is also possible to define random and quantum decision tree complexity of a property, the expected number of questions (for a worst case input) that a randomized or quantum algorithm needs to have answered in order to correctly determine whether the given graph has the property.<ref>See {{harvtxt|Arora|Barak|2009}}, Chapter 12, "Decision trees", pp. 259–269.</ref>

Because the property of containing a clique is monotone, it is covered by the [[Aanderaa–Karp–Rosenberg conjecture]], which states that the deterministic decision tree complexity of determining any non-trivial monotone graph property is exactly {{math|''n''(''n''&nbsp;&minus;&nbsp;1)/2}}. For arbitrary monotone graph properties, this conjecture remains unproven. However, for deterministic decision trees, and for any {{mvar|k}} in the range {{math|2 ≤ ''k'' ≤ ''n''}},  the property of containing a {{mvar|k}}-clique was shown to have decision tree complexity exactly {{math|''n''(''n''&nbsp;&minus;&nbsp;1)/2}} by {{Harvtxt|Bollobás|1976}}. Deterministic decision trees also require exponential size to detect cliques, or large polynomial size to detect cliques of bounded size.<ref>{{harvtxt|Wegener|1988}}.</ref>

The Aanderaa–Karp–Rosenberg conjecture also states that the randomized decision tree complexity of non-trivial monotone functions is {{math|Θ(''n''<sup>2</sup>)}}. The conjecture again remains unproven, but has been resolved for the property of containing a {{mvar|k}} clique for {{math|2 ≤ ''k'' ≤ ''n''}}. This property is known to have randomized decision tree complexity {{math|Θ(''n''<sup>2</sup>)}}.<ref>For instance, this follows from {{Harvtxt|Gröger|1992}}.</ref> For quantum decision trees, the best known lower bound is {{math|Ω(''n'')}}, but no matching algorithm is known for the case of {{math|''k'' ≥ 3}}.<ref>{{harvtxt|Childs|Eisenberg|2005}}; {{harvtxt|Magniez|Santha|Szegedy|2007}}.</ref>