Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Aanderaa–Karp–Rosenberg_conjecture> ?p ?o }
Showing triples 1 to 95 of
95
with 100 triples 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 wikiPageExternalLink citation.cfm?id=1070591.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageExternalLink Groger_1992_ActaCybernetica.pdf.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageExternalLink dtsurvey.pdf.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageExternalLink s00493-010-2485-3.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageExternalLink 120888703.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageID "21681084".
- Aanderaa–Karp–Rosenberg_conjecture wikiPageLength "24871".
- Aanderaa–Karp–Rosenberg_conjecture wikiPageOutDegree "63".
- Aanderaa–Karp–Rosenberg_conjecture wikiPageRevisionID "682463390".
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Algorithm.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Arnold_L._Rosenberg.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Best,_worst_and_average_case.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Big_O_notation.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Bipartite_graph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Category:Combinatorics.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Category:Computational_complexity_theory.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Category:Conjectures.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Category:Graph_theory.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Category:Unsolved_problems_in_computer_science.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Centrum_Wiskunde_&_Informatica.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Combinatorica.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Complete_graph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Conjecture.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Decision_tree_model.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Deterministic_algorithm.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Dover_Publications.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Empty_graph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Erdős–Rényi_model.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Evasive_Boolean_function.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Graph_(mathematics).
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Graph_minor.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Graph_property.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Grovers_algorithm.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Hereditary_property.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Implicit_graph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Journal_of_Computer_and_System_Sciences.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Journal_of_the_ACM.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Las_Vegas_algorithm.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Logical_disjunction.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink László_Lovász.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Minor_(graph_theory).
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Monte_Carlo_algorithm.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Multiset.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Null_graph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Planar_graph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Prime_power.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Quantum_algorithm.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Quantum_query_complexity.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Query_complexity.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Randomized_algorithm.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Regular_graph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Richard_Karp.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Richard_M._Karp.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink SIAM_Journal_on_Computing.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Simple_graph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Society_for_Industrial_and_Applied_Mathematics.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Springer-Verlag.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Springer_Science+Business_Media.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Stål_Aanderaa.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Subgraph_isomorphism.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Subgraph_isomorphism_problem.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Supergraph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Symposium_on_Foundations_of_Computer_Science.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Symposium_on_Theory_of_Computing.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Theoretical_computer_science.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Topological_combinatorics.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Triangle-free_graph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Triangle_finding_problem.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Undirected_graph.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink Worst_case_analysis.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLink File:Scorpion_graph.svg.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageWikiLinkText "Aanderaa–Karp–Rosenberg conjecture".
- Aanderaa–Karp–Rosenberg_conjecture hasPhotoCollection Aanderaa–Karp–Rosenberg_conjecture.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageUsesTemplate Template:Citation.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageUsesTemplate Template:Cite_arXiv.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageUsesTemplate Template:Cite_web.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageUsesTemplate Template:Harv.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageUsesTemplate Template:Harvtxt.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageUsesTemplate Template:Refbegin.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageUsesTemplate Template:Refend.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageUsesTemplate Template:Reflist.
- Aanderaa–Karp–Rosenberg_conjecture wikiPageUsesTemplate Template:Unsolved.
- 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 m.05mt_fn.
- Aanderaa–Karp–Rosenberg_conjecture sameAs Q4661558.
- Aanderaa–Karp–Rosenberg_conjecture sameAs Q4661558.
- Aanderaa–Karp–Rosenberg_conjecture wasDerivedFrom Aanderaa–Karp–Rosenberg_conjecture?oldid=682463390.
- Aanderaa–Karp–Rosenberg_conjecture isPrimaryTopicOf Aanderaa–Karp–Rosenberg_conjecture.