Aanderaa–Karp–Rosenberg conjecture
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 sa
Wikipage disambiguates
AanderaaAanderaa-Karp-Rosenberg conjectureAanderaa-Rosenberg conjectureAanderaa–Rosenberg conjectureArnold L. RosenbergClique problemDecision tree modelEvasive Boolean functionEvasivenessEvasiveness conjectureHereditary propertyImplicit graphJean VuilleminList of unsolved problems in computer scienceRon RivestStål AanderaaSubgraph isomorphism problemTopological combinatoricsValerie King
Link from a Wikipage to another Wikipage
primaryTopic
Aanderaa–Karp–Rosenberg conjecture
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 sa
has abstract
Conjetura de Aanderaa–Karp–Ros ...... a consulta aleatoria cuántica.
@es
In theoretical computer scienc ...... and quantum query complexity.
@en
Гипотеза Аандераа — Карпа — Ро ...... жности по количеству запросов.
@ru
Link from a Wikipage to an external page
Wikipage page ID
21,681,084
page length (characters) of wiki page
Wikipage revision ID
1,000,123,244
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
subject
hypernym
type
comment
Conjetura de Aanderaa–Karp–Ros ...... te, podría tener que examinar
@es
In theoretical computer scienc ...... give its answer. A property sa
@en
Гипотеза Аандераа — Карпа — Ро ...... каждую пару вершин, прежде чем
@ru
label
Aanderaa–Karp–Rosenberg conjecture
@en
Conjetura de Aanderaa-Karp-Rosenberg
@es
Гипотеза Аандераа — Карпа — Розенберга
@ru