Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Aanderaa–Karp–Rosenberg_conjecture> ?p ?o. }
Showing items 1 to 14 of
14
with 100 items per page.
- Aanderaa–Karp–Rosenberg_conjecture abstract "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 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 n(n − 1)/2 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 Rivest & Vuillemin (1975), 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.".
- Aanderaa–Karp–Rosenberg_conjecture wikiPageID "21681084".
- Aanderaa–Karp–Rosenberg_conjecture wikiPageRevisionID "580421103".
- Aanderaa–Karp–Rosenberg_conjecture subject Category:Combinatorics.
- Aanderaa–Karp–Rosenberg_conjecture subject Category:Computational_complexity_theory.
- Aanderaa–Karp–Rosenberg_conjecture subject Category:Conjectures.
- Aanderaa–Karp–Rosenberg_conjecture subject Category:Graph_theory.
- Aanderaa–Karp–Rosenberg_conjecture subject Category:Unsolved_problems_in_computer_science.
- Aanderaa–Karp–Rosenberg_conjecture comment "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 or bipartiteness. They are named after Stål Aanderaa, Richard M. Karp, and Arnold L. Rosenberg.".
- Aanderaa–Karp–Rosenberg_conjecture label "Aanderaa–Karp–Rosenberg conjecture".
- Aanderaa–Karp–Rosenberg_conjecture sameAs Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture.
- Aanderaa–Karp–Rosenberg_conjecture sameAs Q4661558.
- Aanderaa–Karp–Rosenberg_conjecture sameAs Q4661558.
- Aanderaa–Karp–Rosenberg_conjecture wasDerivedFrom Aanderaa–Karp–Rosenberg_conjecture?oldid=580421103.