About: Aanderaa–Karp–Rosenberg conjecture

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Aanderaa–Karp–Rosenberg conjecture Goto Sponge NotDistinct Permalink

An Entity of Type : yago:State100024720, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FAanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture&invfp=IFP_OFF&sas=SAME_AS_OFF

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 and vertex ?" 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 sati

Attributes	Values
rdf:type	yago:WikicatConjectures yago:WikicatUnsolvedProblemsInComputerScience yago:Abstraction100002137 yago:Attribute100024264 yago:Cognition100023271 yago:Concept105835747 yago:Condition113920835 yago:Content105809192 yago:Difficulty114408086 yago:Hypothesis105888929 yago:Idea105833840 yago:Problem114410605 yago:PsychologicalFeature100023100 Band yago:Speculation105891783 yago:State100024720
rdfs:label	Aanderaa–Karp–Rosenberg conjecture (en) Conjetura de Aanderaa-Karp-Rosenberg (es) Conjecture d'Aanderaa-Karp-Rosenberg (fr) Гипотеза Аандераа — Карпа — Розенберга (ru)
rdfs: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 and vertex ?" 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 sati (en) Conjetura de Aanderaa–Karp–Rosenberg En la ciencia de la computación teórica, la conjetura Aanderaa-Karp-Rosenberg (también conocida como la conjetura Aanderaa-Rosenberg o la conjetura evasivas) es un grupo de conjeturas relacionadas sobre el número de preguntas del tipo "¿Hay un borde entre el vértice "u" y el vértice "v"? que tienen que ser respondidas para determinar si un grafo no dirigido tiene una propiedad particular, como la planitud o bipartiteness. Llevan el nombre de Stål Aanderaa, Richard M. Karp, y Arnold L. Rosenberg. Según la conjetura, para una amplia clase de propiedades, ningún algoritmo puede garantizar que será capaz de saltarse cualquier pregunta: cualquier algoritmo para determinar si la gráfica tiene la propiedad, no importa lo inteligente, podría tener que examinar (es) En informatique théorique, la conjecture d'Aanderaa-Karp-Rosenberg (aussi connue sous le nom de conjecture d'Aanderaa-Rosenberg ou conjecture de l'évasion) est un ensemble de conjectures concernant le nombre de questions de la forme « existe-t-il une arête entre le sommet et sommet ? » dans un graphe auxquelles il faut répondre pour déterminer si oui ou non un graphe non orienté possède une propriété donnée telle que la planarité ou le caractère biparti . Elles portent les noms de Stål Aanderaa, Richard M. Karp et Arnold L. Rosenberg. La conjecture affirme que, pour une large classe de propriétés, tout algorithme pour déterminer si un graphe possède une de ces propriétés, aussi élaboré soit-il, peut être amené à examiner toute paire de sommets avant de donner sa réponse. Une propriété sa (fr) Гипотеза Аандераа — Карпа — Розенберга (известная также как гипотеза Аандераа — Розенберга или гипотеза трудности) — это группа связанных гипотез о числе вопросов в форме «Имеется ли ребро между вершиной u и вершиной v?», на которые следует ответить, чтобы определить, обладает или нет неориентированный граф определённым свойством (инвариантом), таким как планарность или двудольность. Гипотеза названа именами норвежского математика Стола Аандераа и американских учёных Ричарда М. Карпа и Арнольда Л. Розенберга. Согласно гипотезе, для широкого класса инвариантов никакой алгоритм не может гарантировать, что алгоритм может опустить какой-либо запрос — любой алгоритм определения, обладает ли граф свойством, неважно, насколько умён этот алгоритм, он должен проверить каждую пару вершин, прежде чем (ru)
foaf:depiction
dcterms:subject	Conjectures Combinatorics Unsolved problems in computer science Computational complexity theory Graph theory
Wikipage page ID	21681084 (xsd:integer)
Wikipage revision ID	1076850209 (xsd:integer)
Link from a Wikipage to another Wikipage	Prime power Minor (graph theory) Monte Carlo algorithm Algorithm Regular graph Richard M. Karp Undirected graph Deterministic algorithm Topological combinatorics Conjectures Complete graph Quantum algorithm Glossary of graph theory Graph (discrete mathematics) Multiset Conjecture Erdős–Rényi model SIAM Journal on Computing Arnold L. Rosenberg Stål Aanderaa Combinatorica Theoretical computer science Centrum Wiskunde & Informatica Las Vegas algorithm Lecture Notes in Computer Science Combinatorics Unsolved problems in computer science Graph property Journal of Computer and System Sciences Journal of the ACM Logical disjunction Computational complexity theory Graph theory Big O notation Bipartite graph Hereditary property Dover Publications Planar graph Society for Industrial and Applied Mathematics Grover's algorithm Empty graph Implicit graph Randomized algorithm Evasive Boolean function Worst case analysis Triangle finding problem Richard Karp Springer-Verlag Simple graph SIGACT News Quantum query complexity Query complexity Subgraph isomorphism
Link from a Wikipage to an external page	http://www.math.rutgers.edu/~saks/PUBS/dtsurvey.pdf https://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf http://portal.acm.org/citation.cfm%3Fid=1070591
sameAs	Aanderaa–Karp–Rosenberg conjecture Aanderaa–Karp–Rosenberg conjecture Aanderaa–Karp–Rosenberg conjecture Aanderaa–Karp–Rosenberg conjecture Aanderaa–Karp–Rosenberg conjecture Aanderaa–Karp–Rosenberg conjecture
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Cite_arXiv dbt:Harv dbt:Harvtxt dbt:Refbegin

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software