Aanderaa–Karp–Rosenberg conjecture
Must every deterministic algorithm for a non-trivial monotone graph property ask about every pair of vertices in the worst case?
Summary
Why it is open
The model is the decision tree: the algorithm chooses each question from the answers so far, and its cost is the number of questions in the worst case [9]. A graph property gives the same answer for graphs that differ only in the labels of their vertices [9]. A graph on n vertices has n(n−1)/2 vertex pairs, so no property needs more questions than that, and a property that needs exactly that many is called evasive [4]. A property is monotone if adding edges never destroys it (or, for the decreasing version, removing edges never does), and nontrivial if some graph on n vertices has it and some does not [4, 9]. Connectedness, non-planarity, non-k-colourability and containing a perfect matching are examples, for large enough n [4].
The problem has two layers. In 1973 Aanderaa and Arnold Rosenberg conjectured that monotone graph properties need a number of questions of the order of n², and R. Karp conjectured the stronger statement that every nontrivial monotone graph property is evasive [7, 9]; Rosenberg's 1973 note attributes the stronger conjecture to Karp [4]. The weaker conjecture was proved in the 1970s [4, 7]. The stronger one, the evasiveness conjecture and the subject of this page, has been proved when n is a prime power and for several classes of properties [4, 9], and Carl Miller's 2013 survey reports no known counterexample [9]. In 2019 Andrés Ángel and Jerson Borja wrote that it had also been proved for six vertices and that ten vertices was still unsolved [11].
A resolution would be a proof for every n, or a nontrivial monotone property on some number of vertices that can be decided with fewer questions. Kahn, Saks and Sturtevant showed that such a property would have a special topological structure, described below [9]. Randomised and quantum versions are separate questions [12]. No prize or committee sets further terms; the status here follows Wikipedia's list of unsolved problems in computer science [13].
What is known
Quadratic lower bounds (1976–2013). Ronald Rivest and Jean Vuillemin proved that every nontrivial monotone graph property needs at least n²/16 questions, settling the Aanderaa–Rosenberg conjecture [1, 4, 7]. D. J. Kleitman and D. J. Kwiatkowski raised the bound to n²/9 in 1980 [7, 9]. Later bounds have the form cn² − o(n²), where o(n²) is a term that becomes negligible next to n² as n grows: c = 1/4 from Jeff Kahn, Michael Saks and Dean Sturtevant in 1984 [9], c = 8/25 from Torsten Korneffel and Eberhard Triesch [8, 9], and c = 1/3 from Robert Scheidweiler and Triesch [10]. In 2021 Scott Aaronson and colleagues still described the last as the best current result [12].
The topological method (1984–2002). Kahn, Saks and Sturtevant associated with a monotone property a simplicial complex, a collection of sets closed under taking subsets that can be read as a geometric shape, built from the graphs that lack the property [9]. They showed that if the property is not evasive, the complex is collapsible: it can be folded into itself and contracted to a single point [9]. A fixed-point theorem of R. Oliver then forces certain group actions on the complex to fix a point; when n is a prime power, a group can be chosen whose only invariant graphs are the empty and the complete graph, which proves the conjecture for those n [2, 9]. Andrew Chi-Chih Yao proved that every nontrivial monotone property of bipartite graphs, on a fixed pair of vertex sets, is evasive [3]. Amit Chakrabarti, Subhash Khot and Yaoyun Shi proved that containing a fixed graph H as a subgraph is evasive for an arithmetic progression of values of n, with complexity n²/2 − O(n) in general, and that every nontrivial property preserved under taking graph minors, such as planarity, is evasive for all sufficiently large n [4].
Number theory enters (2010). László Babai, Anandam Banerjee, Raghav Kulkarni and Vipul Naik proved that the property of not containing a fixed graph H needs n(n−1)/2 − O(1) questions for every n, and that it is evasive for all sufficiently large n if a weak form of a conjecture of Chowla on primes in arithmetic progressions holds [7]. They also proved, unconditionally, that nontrivial monotone properties which fail for every graph with more than cn log n edges, for some constant c > 0, are evasive for all sufficiently large n [7]. Under Chowla's conjecture the edge bound becomes n^(3/2−ε), and under the Extended Riemann Hypothesis, the Riemann hypothesis for Dirichlet L-functions, it becomes n^(5/4−ε) [7]. Even the unconditional results rely on deep number theory, such as Vinogradov's theorem on the Goldbach conjecture [7].
Randomised and quantum versions (1977–2021). A randomised decision tree may choose its questions at random, and its cost is the expected number of questions on the worst input [9]. The conjecture that randomised algorithms still need of the order of n² questions is attributed to Karp and, in a 1977 paper, to Yao [12]. Lower bounds rose through Valerie King's bound of order n^(5/4) and Péter Hajnal's of order n^(4/3) to Chakrabarti and Khot's n^(4/3)(log n)^(1/3) [6, 12], which Aaronson and colleagues gave as the current best bound in 2021 [12]. Ryan O'Donnell, Saks, Oded Schramm and Rocco Servedio proved a bound of order v^(4/3)/p^(1/3), with v vertices and p ≤ 1/2 the critical threshold probability, which is sometimes better [5]. A quantum algorithm may query a superposition of vertex pairs, and its probability of error must stay below a fixed bound on every input [9]. Because the property "contains at least one edge" can be decided with of the order of n quantum queries by Grover's quantum search algorithm, Harry Buhrman, Richard Cleve, Ronald de Wolf and Christof Zalka asked whether every nontrivial monotone graph property needs that many, and proved a bound of order √n [12]. Building on Hao Huang's 2019 proof of the sensitivity conjecture, Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao and Avishay Tal proved in 2021 that every nontrivial monotone graph property needs of the order of n quantum queries, which they describe as resolving the quantum analogue of the conjecture [12].
Main approaches
Adversary arguments. An adversary answers each question so that the outcome stays open until the last pair [4, 9]. Strongest evidence: evasiveness for all n of acyclicity, connectedness, 2-connectedness, planarity and, in Bollobás's strategy, containing a k-clique [4]. Main difficulty: each strategy is built for one property and simple variants of it [4].
Topology and group actions. Non-evasiveness implies collapsibility, which is stronger than the earlier counting condition that a non-evasive property contains equally many graphs with an odd and with an even number of edges [9]. Strongest evidence: the prime-power case [2, 9], the bipartite case [3] and the n²/3 bound [10]. Main difficulty: for n just above a prime p there is "no known way" to show that the complexity stays at least p(p−1)/2, Miller writes; he adds that stronger results have come with steeply harder proofs, and that "Perhaps a new basic insight" will be necessary [9].
Primes in arithmetic progressions. Combine the topological framework with an analysis of permutation groups whose usefulness depends on the distribution of prime numbers [7]. Strongest evidence: the unconditional n(n−1)/2 − O(1) bound for forbidden subgraphs and the sparse-graph results [7]. Main difficulty: the strongest statements depend on Chowla's conjecture, which is not known to follow from the Extended Riemann Hypothesis, and even the unconditional ones need deep results in number theory [7].
Polynomials and influences. Bound query complexity through the degree of polynomials representing the property or through the influence of single edges [5, 12]. Strongest evidence: the optimal quantum bound, which combines a quadratic lower bound on the degree of monotone graph properties over the two-element field with a consequence of Huang's theorem [12], and the influence bound for randomised trees [5]. Main difficulty: in 2005 O'Donnell and colleagues noted that the randomised bound had been "stuck for almost 15 years" at about v^(4/3), which "is exactly the tight bound for monotone transitive functions", a wider class that includes graph properties [5].
Open sub-questions
- Ten vertices. Is every nontrivial monotone property of graphs on ten vertices evasive, and can the necessary conditions that Ángel and Borja derive for a counterexample be checked exhaustively [11]?
- Beyond one third. Can group actions of the kind used by Korneffel and Triesch and by Scheidweiler and Triesch give a general lower bound above n²/3 − o(n²) [8, 10]?
- Forbidden subgraphs without Chowla. Can the forbidden-subgraph property be shown evasive for all sufficiently large n without the weak Chowla conjecture [7]?
- Denser sparse properties. Can the unconditional edge threshold of cn log n be raised towards n^(3/2−ε) without number-theoretic conjectures [7]?
- Randomised complexity. Can an argument that uses more than the symmetry shared by monotone transitive functions improve the n^(4/3)(log n)^(1/3) randomised bound for graph properties [5, 6]?
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Rivest, R. L. & Vuillemin, J. (1976). On recognizing graph properties from adjacency matrices. Theoretical Computer Science 3(3), 371–384. 10.1016/0304-3975(76)90053-0 · Checked 16 Oct 2026
- Kahn, J., Saks, M. & Sturtevant, D. (1984). A topological approach to evasiveness. Combinatorica 4(4), 297–306. 10.1007/BF02579140 · Checked 16 Oct 2026
- Yao, A. C.-C. (1988). Monotone bipartite graph properties are evasive. SIAM Journal on Computing 17(3), 517–520. 10.1137/0217031 · Checked 16 Oct 2026
- Chakrabarti, A., Khot, S. & Shi, Y. (2002). Evasiveness of subgraph containment and related properties. SIAM Journal on Computing 31(3), 866–875 (Crossref gives the issue date as January 2001; the article states publication in January 2002). 10.1137/S0097539700382005 · Checked 16 Oct 2026
- O'Donnell, R., Saks, M., Schramm, O. & Servedio, R. A. (2005). Every decision tree has an influential variable. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 31–39. 10.1109/SFCS.2005.34 · Checked 16 Oct 2026
- Chakrabarti, A. & Khot, S. (2007). Improved lower bounds on the randomized complexity of graph properties. Random Structures & Algorithms 30(3), 427–440. 10.1002/rsa.20164 · Checked 16 Oct 2026
- Babai, L., Banerjee, A., Kulkarni, R. & Naik, V. (2010). Evasiveness and the distribution of prime numbers. In 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), LIPIcs 5, 71–82. 10.4230/LIPIcs.STACS.2010.2445 · Checked 16 Oct 2026
- Korneffel, T. & Triesch, E. (2010). An asymptotic bound for the complexity of monotone graph properties. Combinatorica 30(6), 735–743. 10.1007/s00493-010-2485-3 · Checked 16 Oct 2026
- Miller, C. A. (2013). Evasiveness of graph properties and topological fixed-point theorems. Foundations and Trends in Theoretical Computer Science 7(4), 337–415 (volume dated 2011). 10.1561/0400000055 · Checked 16 Oct 2026
- Scheidweiler, R. & Triesch, E. (2013). A lower bound for the complexity of monotone graph properties. SIAM Journal on Discrete Mathematics 27(1), 257–265. 10.1137/120888703 · Checked 16 Oct 2026
- Ángel, A. & Borja, J. (2019). The evasiveness conjecture and graphs on 2p vertices. Journal of Graph Theory 91(1), 35–52; published online 2018. 10.1002/jgt.22419 · Checked 16 Oct 2026
- Aaronson, S., Ben-David, S., Kothari, R., Rao, S. & Tal, A. (2021). Degree vs. approximate degree and quantum implications of Huang's sensitivity theorem. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), 1330–1342. 10.1145/3406325.3451047 · Checked 16 Oct 2026
- Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.