to correctly determine whether the given graph has the property. 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 . For arbitrary monotone graph properties, this conjecture remains unproven. However, for deterministic decision trees, and for any in the range , the property of containing a -clique was shown to have decision tree complexity exactly by . Deterministic decision trees also require exponential size to detect cliques, or large polynomial size to detect cliques of bounded size. The Aanderaa–Karp–Rosenberg conjecture also states that the randomized decision tree complexity of non-trivial monotone functions is . The conjecture again remains unproven, but has been resolved for the property of containing a clique for . This property is known to have randomized decision tree complexity . For quantum decision trees, the best known lower bound is , but no matching algorithm is known for the case of . Fixed-parameter intractability Parameterized complexity is the complexity-theoretic study of problems that are naturally equipped with a small integer parameter and for which the problem becomes more difficult as increases, such as finding -cliques in graphs. A problem is said to be fixed-parameter tractable if there is an algorithm for solving it on inputs of size , and a function , such that the algorithm runs in time . That is, it is fixed-parameter tractable if it can be solved in polynomial time for any fixed value of and moreover if the exponent of the polynomial does not depend on . For finding -vertex cliques, the brute force search algorithm has running time . Because the exponent of depends on , this algorithm is not fixed-parameter tractable. Although it can be improved by fast matrix multiplication the running time still has an exponent that is linear in Thus, although the running time of known algorithms for the clique problem is polynomial for any fixed , these algorithms do not suffice for fixed-parameter tractability. defined a hierarchy of parametrized problems, the W hierarchy, that they conjectured did not have fixed-parameter tractable algorithms. They proved that independent set (or, equivalently, clique) is hard for the first level of this hierarchy, W[1]. Thus, according to their conjecture, clique has no fixed-parameter tractable algorithm. Moreover, this result provides the basis for proofs of W[1]-hardness of many