Aanderaa–Karp–Rosenberg conjecture
In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture (also known as the Aanderaa–Rosenberg conjecture or the evasiveness conjecture) is a group of related conjectures about the number of questions of the form "Is there an edge between vertex formula_1 and vertex formula_2?" that have to be answered to determine whether or not an undirected graph has a particular property such as planarity or bipartiteness. They are named after Stål Aanderaa, Richard M. Karp, and Arnold L. Rosenberg. According to the conjecture, for a wide class of properties, no algorithm can guarantee that it will  be able to skip any questions: any algorithm for determining whether the graph has the property, no matter how clever, might need to examine every pair of vertices before it can give its answer. A property satisfying this conjecture is called evasive. More precisely, the Aanderaa–Rosenberg conjecture states that any deterministic algorithm must test at least a constant fraction of all possible pairs of vertices, in the worst case, to determine any non-trivial monotone graph property; in this context, a property is monotone if it remains true when edges are added (so planarity is not monotone, but non -planarity is monotone). A stronger version of this conjecture, called the evasiveness conjecture or the Aanderaa–Karp–Rosenberg conjecture, states that exactly formula_3 tests are needed. Versions of the problem for randomized algorithms and quantum algorithms have also been formulated and studied. The deterministic Aanderaa–Rosenberg conjecture was proven by , but the stronger Aanderaa–Karp–Rosenberg conjecture remains unproven. Additionally, there is a large gap between the conjectured lower bound and the best proven lower bound for randomized and quantum query complexity. Example. The property of being non-empty (that is, having at least one edge) is monotone, because adding  another edge to a non-empty graph produces another non-empty graph. There is a simple algorithm for testing whether a graph is non-empty: loop through all of the pairs of vertices, testing whether each pair is connected by an edge. If an edge is ever found in this way, break out of the loop, and report that the graph is non-empty, and if the loop completes without finding any edges, then report that the graph is empty. On some graphs (for instance the complete graphs) this algorithm will terminate quickly, without testing every pair of vertices, but  on the empty graph it tests all possible pairs before terminating. Therefore, the query complexity of this algorithm is formula_3: in the worst case, the algorithm performs formula_5 tests. The algorithm described above is not the only possible method of testing for non-emptiness, but the Aanderaa–Karp–Rosenberg conjecture implies that every deterministic algorithm for testing non-emptiness has the same worst-case query complexity, formula_5. That is, the property of being non-empty is "evasive". For this property, the result is easy to prove directly: if an algorithm does not perform formula_5 tests, it cannot distinguish the  empty graph from a graph that has one edge connecting one of the untested pairs of vertices, and must give an incorrect answer on one of these two graphs. Definitions. In the context of this article, all graphs will be simple and undirected, unless stated otherwise. This means that the edges of the graph form a set (and not a multiset) and each edge is a pair of distinct vertices. Graphs are assumed to have an implicit representation in which each vertex has a unique identifier or label and in which it is possible to test the adjacency of any  two vertices, but for which adjacency testing is the only allowed primitive operation. Informally, a graph property is a property of a graph that is independent of labeling. More formally, a graph property is a mapping from the class of all graphs to formula_8 such that isomorphic graphs are mapped to the same value. For example, the property of containing at least one vertex of degree two is a graph property, but the property that the first vertex has degree two is not, because it depends on the labeling of the graph (in particular, it depends on which vertex is  the "first" vertex). A graph property is called non-trivial if it does not assign the same value to all graphs. For instance, the property of being a graph is a trivial property, since all graphs possess this property. On the other hand, the property of being empty is non-trivial, because the empty graph possesses this property, but non-empty graphs do not. A graph property is said to be monotone if the addition of edges does not destroy the property. Alternately, if a graph possesses a monotone property, then every supergraph of this graph on the same vertex  set also possesses it. For instance, the property of being nonplanar is monotone: a supergraph of a nonplanar graph is itself nonplanar. However, the property of being regular is not monotone. The big O notation is often used for query complexity. In short, formula_9 is formula_10 (read as "of the order of formula_11") if there exist positive constants formula_12 and formula_13 such that, for all formula_14, formula_15. Similarly, formula_9 is formula_17 if there exist positive constants formula_12 and formula_13 such that, for all formula_14, formula_21. Finally, formula_9 is formula_23 if it is both formula_10 and formula_17. Query complexity. The deterministic  query complexity of evaluating a function on formula_26 bits (where the bits may be labeled as formula_27) is the number of bits formula_28 that have to be read in the worst case by a deterministic algorithm that computes the function. For instance, if the function takes the value 0 when all bits are 0 and takes value 1 otherwise (this is the OR function), then its deterministic query complexity is exactly formula_26. In the worst case, regardless of the order it chooses to examine its input, the first formula_30 bits read could all be 0, and the value of the  function now depends on the last bit. If an algorithm doesn't read this bit, it might output an incorrect answer. (Such arguments are known as adversary arguments.) The number of bits read are also called the number of queries made to the input. One can imagine that the algorithm asks (or queries) the input for a particular bit and the input responds to this query. The randomized query complexity of evaluating a function is defined similarly, except the algorithm is allowed to be randomized. In other words, it can flip coins and use the outcome of these coin flips  to decide which bits to query in which order. However, the randomized algorithm must still output the correct answer for all inputs: it is not allowed to make errors. Such algorithms are called Las Vegas algorithms. (A different class of algorithms, Monte Carlo algorithms, are allowed to make some error.) Randomized query complexity can be defined for both Las Vegas and Monte Carlo algorithms, but the randomized version of the Aanderaa–Karp–Rosenberg conjecture is about the Las Vegas query complexity of graph properties. Quantum query complexity is the natural generalization of randomized query complexity, of course allowing quantum queries  and responses. Quantum query complexity can also be defined with respect to Monte Carlo algorithms or Las Vegas algorithms, but it is usually taken to mean Monte Carlo quantum algorithms. In the context of this conjecture, the function to be evaluated is the graph property, and the input can be thought of as a string of size formula_5, describing for each pair of vertices whether there is an edge with that pair as its endpoints. The query complexity of any function on this input is at most formula_5, because an algorithm that makes formula_5 queries can read the whole input  and determine the input graph completely. Deterministic query complexity. For deterministic algorithms, originally conjectured that for all nontrivial graph properties on formula_26 vertices, deciding whether a graph possesses this property requires formula_35 The non-triviality condition is clearly required because there are trivial properties like "is this a graph?" which can be answered with no queries at all. The conjecture was disproved by Aanderaa, who exhibited a directed graph property (the property of containing a "sink") which required only formula_36 queries to test. A "sink", in a directed graph, is a vertex of indegree formula_30 and outdegree zero. The existence  of a sink can be tested with less than formula_38 queries . An undirected graph property which can also be tested with formula_36 queries is the property of being a scorpion graph, first described in . A scorpion graph is a graph containing a three-vertex path, such that one endpoint of the path is connected to all remaining vertices, while the other two path vertices have no incident edges other than the ones in the path. Then Aanderaa and Rosenberg formulated a new conjecture (the Aanderaa–Rosenberg conjecture) which says that deciding whether a graph possesses a non-trivial monotone graph  property requires formula_35 queries. This conjecture was resolved by by showing that at least formula_41 queries are needed to test for any nontrivial monotone graph property. The bound was further improved to formula_42 by , to formula_43 (for any formula_44) by , to formula_45 by , and to formula_46 by . Richard Karp conjectured the stronger statement (which is now called the evasiveness conjecture or the Aanderaa–Karp–Rosenberg conjecture) that "every nontrivial monotone graph property for graphs on formula_26 vertices is evasive." A property is called "evasive" if determining whether a given graph has this property sometimes requires all formula_5 possible queries. This  conjecture says that the best algorithm for testing any nontrivial monotone property must (in the worst case) query all possible edges. This conjecture is still open, although several special graph properties have shown to be evasive for all formula_26. The conjecture has been resolved for the case where formula_26 is a prime power by using a topological approach. The conjecture has also been resolved for all non-trivial monotone properties on bipartite graphs by . Minor-closed properties have also been shown to be evasive for large formula_26 . In the conjecture was generalized to properties of other (non-graph) functions too , conjecturing that any non-trivial monotone function that is weakly symmetric is evasive. This case is also solved when formula_26 is a prime power . Randomized query complexity. Richard Karp also conjectured that formula_35 queries are required for testing nontrivial monotone properties even if randomized algorithms are permitted. No nontrivial monotone property is known which requires less than formula_54 queries to test. A linear lower bound (i.e., formula_55) on all monotone properties follows from a very general relationship between randomized and deterministic query complexities. The first superlinear lower bound for all monotone properties was given by who showed that formula_56 queries  are required. This was further improved by to formula_57, and then by This was subsequently improved to the current best known lower bound (among bounds that hold for all monotone properties) of formula_58 by . Some recent results give lower bounds which are determined by the critical probability formula_59 of the monotone graph property under consideration. The critical probability formula_59 is defined as the unique number formula_59 in the range formula_62 such that a random graph formula_63 (obtained by choosing randomly whether each edge exists, independently of the other edges, with probability formula_59 per edge) possesses this property with probability equal  to formula_65. showed that any monotone property with critical probability formula_59 requires formula_67 queries. For the same problem, showed a lower bound of formula_68. As in the deterministic case, there are many special properties for which an formula_35 lower bound is known. Moreover, better lower bounds are known for several classes of graph properties. For instance, for testing whether the graph has a subgraph isomorphic to any given graph (the so-called subgraph isomorphism problem), the best known lower bound is formula_70 due to . Quantum query complexity. For bounded-error quantum query complexity, the best known lower bound is formula_71  as observed by Andrew Yao. It is obtained by combining the randomized lower bound with the quantum adversary method. The best possible lower bound one could hope to achieve is formula_55, unlike the classical case, due to Grover's algorithm which gives an formula_36-query algorithm for testing the monotone property of non-emptiness. Similar to the deterministic and randomized case, there are some properties which are known to have an formula_55 lower bound, for example non-emptiness (which follows from the optimality of Grover's algorithm) and the property of containing a triangle. There are some graph properties which  are known to have an formula_70 lower bound, and even some properties with an formula_35 lower bound. For example, the monotone property of nonplanarity requires formula_77 queries and the monotone property of containing more than half the possible number of edges (also called the majority function) requires formula_78 queries .