This HTML5 document contains 238 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Subject Item

dbpedia-es:Conjetura_de_Aanderaa-Karp-Rosenberg

rdfs:label

Conjetura de Aanderaa-Karp-Rosenberg

rdfs:comment

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

dct:subject

category-es:Conjeturas_matemáticas

foaf:isPrimaryTopicOf

wikipedia-es:Conjetura_de_Aanderaa-Karp-Rosenberg

prop-es:arxiv

quant-ph/0310134

prop-es:author1Link

Daniel Kleitman

prop-es:author2Link

Peter van Emde Boas Michael Saks Subhash Khot

prop-es:author3Link

Hendrik Lenstra Oded Schramm Mario Szegedy

prop-es:authorlink

Arnold L. Rosenberg Andrew Yao Michele Mosca Ron Rivest Avi Wigderson Richard Cleve Andris Ambainis

prop-es:booktitle

dbpedia-es:Symposium_on_Foundations_of_Computer_Science

prop-es:chapter

A topological approach to evasiveness Computing Graph Properties by Randomized Subcube Partitions

prop-es:contribution

Every decision tree has an influential variable Improved Lower Bounds on the Randomized Complexity of Graph Properties Quantum query complexity of Boolean functions with small on-sets Lower bounds on the complexity of graph properties A generalization and proof of the Aanderaa-Rosenberg conjecture Quantum algorithms for the triangle problem

prop-es:doi

101016 101006 101007 101109 101137 101145

prop-es:fechaacceso

16

prop-es:fechaarchivo

24

prop-es:first

Harumichi Jean Robert Ronald L. D.J. Seiichiro Arnold L. Hans Dietmar Ryan H.W. Masaki Michael Torsten Andrew Chi-Chih Harry Dean Frédéric Ehud DJ Frank H. Andris Michele Péter Yaoyun Subhash Jeff Shigeru Mario Valerie Avi Ronald Miklos Rocco A. Dmitry Kazuo Oded M.R. Richard P. Eberhard Amit Rudy

prop-es:isbn

0 978

prop-es:issn

209

prop-es:issue

4 6 1 2 3

prop-es:journal

dbpedia-es:Combinatorica dbpedia-es:SIAM_Journal_on_Computing Acta Cybernetica Combinatorica SIAM Journal on Discrete Mathematics Journal of Combinatorial Theory, Series B Journal of Combinatorial Theory. Series B dbpedia-es:Journal_of_the_ACM SIGACT News dbpedia-es:Journal_of_Computer_and_System_Sciences

prop-es:last

Shi Rivest Wigderson Magniez Szegedy Yamashita Triesch Rosenberg Iwama van Emde Boas O'Donnell Santha King Ambainis Kahn Vuillemin Sturtevant Lenstra Cleve Beals Friedgut Lutz Korneffel Scheidweiler Nakanishi de Wolf Chakrabarti Kwiatkowski Hajnal Servedio Best Buhrman Schramm Yao Tani Nishimura Saks Kleitman Khot Raymond Mosca Gröger Kozlov

prop-es:location

Chicago, Illinois, United States Albuquerque, New Mexico, United States Vancouver, British Columbia Los Alamitos, CA, USA Gold Coast, Australia

prop-es:number

1

prop-es:page

953

prop-es:pages

85 517 866 131 468 907 1109 735 285 267 31 259 257 15 6 119 778 110

prop-es:publisher

dbpedia-es:Sociedad_de_Matemáticas_Aplicadas_e_Industriales Springer-Verlag n16:Business_Media n17:_Informatica IEEE Computer Society

prop-es:series

Report ZW 30/74 Lecture Notes in Computer Science

prop-es:title

Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms dbpedia-es:Symposium_on_Foundations_of_Computer_Science An asymptotic bound for the complexity of monotone graph properties Randomization and Approximation Techniques in Computer Science On the time required to recognize properties of graphs: a problem Combinatorial Algebraic Topology On the randomized complexity of monotone graph properties Some results related to the evasiveness conjecture Monotone bipartite graph properties are evasive Evasiveness of subgraph containment and related properties Further results on the Aanderaa-Rosenberg conjecture An Ω lower bound on the randomized complexity of graph properties Proceedings of the 28th International Colloquium on Automata, Languages and Programming Quantum lower bounds by polynomials A sharpened version of the Aanderaa-Rosenberg conjecture Proceedings of the 19th International Symposium on Algorithms and Computation 24 A Lower Bound for the Complexity of Monotone Graph Properties Lower bounds to randomized algorithms for graph properties dbpedia-es:Symposium_on_Theory_of_Computing On the recognition complexity of some graph properties

prop-es:url

n11:s00493-010-2485-3 n15:1070591 n13:120888703 n18:pdf

prop-es:urlarchivo

n14:pdf

prop-es:volume

81 2483 42 48 10 11 5 27 28 30 31 16 17 5369 2076

prop-es:year

1991 1988 1983 1980 1974 1975 1973 2010 2008 2013 2002 2001 2005 1992 1996

dbo:wikiPageID

6467947

dbo:wikiPageRevisionID

124471342

dbo:wikiPageExternalLink

n13:120888703 n14:pdf n11:s00493-010-2485-3 n15:1070591 n18:pdf

dbo:wikiPageLength

14387

prov:wasDerivedFrom

n5:0

dbo:abstract

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 cada par de vértices antes de que pueda dar su respuesta. Una propiedad satisfacer esta conjetura se llama evasiva. Más precisamente, la conjetura Aanderaa-Rosenberg afirma que cualquier algoritmo determinista debe probar al menos una fracción constante de todos los posibles pares de vértices, en el peor de los casos, para determinar cualquier propiedad gráfica monótona no trivial; en este contexto, una propiedad es monótona si sigue siendo cierto cuando se añaden bordes (tan planitud no es monótona, pero no planaridad es monótona). Una versión más fuerte de esta conjetura, llamada la conjetura evasivas o la conjetura Aanderaa-Karp-Rosenberg, afirma que exactamente n (n - 1) / 2 se necesitan pruebas. Las versiones del problema de algoritmos aleatorios y algoritmos cuánticos también se han formulado y estudiado. La determinación de la conjetura de Aanderaa-Rosenberg fue probada por Rivest y Vuillemin (1975), pero la más fuerte conjetura Aanderaa-Karp-Rosenberg sigue sin comprobarse. Además, hay una gran brecha entre el conjeturado límite inferior y el mejor demostrado límite inferior para la complejidad consulta aleatorizado y cuántica. 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 vértice "v"? "que tienen que ser respondidas para determinar si un grafo no dirigido tiene una propiedad particular, como la planitud o bipartiteness. Ellos 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 cada par de vértices antes de que pueda dar su respuesta. Una propiedad satisfacer esta conjetura se llama evasiva. Más precisamente, la conjetura Aanderaa-Rosenberg afirma que cualquier algoritmo determinista debe probar al menos una fracción constante de todos los posibles pares de vértices, en el peor de los casos, para determinar cualquier propiedad gráfica monótona no trivial; en este contexto, una propiedad es monótona si sigue siendo cierto cuando se añaden bordes (tan planitud no es monótona, pero no planaridad es monótona). Una versión más fuerte de esta conjetura, llamada la conjetura evasivas o la conjetura Aanderaa-Karp-Rosenberg, afirma que exactamente n (n - 1) / 2 se necesitan pruebas. Las versiones del problema de algoritmos aleatorios y algoritmos cuánticos también se han formulado y estudiado. El determinista conjetura Aanderaa-Rosenberg fue probada por Rivest y Vuillemin (1975), pero la más fuerte conjetura Aanderaa-Karp-Rosenberg sigue sin comprobarse. Además, hay una gran brecha entre el conjeturado límite inferior y el mejor demostrado límite inferior para la compleja consulta aleatoria cuántica.

Subject Item

wikipedia-es:Conjetura_de_Aanderaa-Karp-Rosenberg

foaf:primaryTopic

dbpedia-es:Conjetura_de_Aanderaa-Karp-Rosenberg