---
tag: Q74KEMA8TE
kind: conjecture
name: Aanderaa–Karp–Rosenberg conjecture
aliases: [aanderaa-rosenberg-conjecture, evasiveness, evasiveness-conjecture]
sources:
  - wikipedia: en:21681084@r1375125283
    locator: Aanderaa–Karp–Rosenberg conjecture
    note: adopted
    mention: wikipedia://en/21681084
    sections: [Statement]
same_as:
  wikidata: Q4661558
  wikipedia: Aanderaa–Karp–Rosenberg conjecture
inventory: [5BCATZT2HV]
---

## Statement

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 $u$ and vertex $v$?" that have to be answered to determine whether or not an undirected graph has a particular property such as [[planarity|029JQEK15B]] or [[bipartiteness|07DVHJ8N0A]]. 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.