Papex

Open problem · Computer science · Open

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

Also called the evasiveness conjecture, it concerns how many “is there an edge here?” queries are needed to decide properties such as connectivity. It is proved when the number of vertices is a prime power, but open in general.

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

  1. 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]?
  2. 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]?
  3. Forbidden subgraphs without Chowla. Can the forbidden-subgraph property be shown evasive for all sufficiently large n without the weak Chowla conjecture [7]?
  4. Denser sparse properties. Can the unconditional edge threshold of cn log n be raised towards n^(3/2−ε) without number-theoretic conjectures [7]?
  5. 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

  1. 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
  2. Kahn, J., Saks, M. & Sturtevant, D. (1984). A topological approach to evasiveness. Combinatorica 4(4), 297–306. 10.1007/BF02579140 · Checked 16 Oct 2026
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. Á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
  12. 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
  13. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026

Page reviewed 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.

More in Computing