| Property |
Value |
| 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. (es)
- 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. (es)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| prop-es:arxiv
|
- quant-ph/0310134 (es)
- quant-ph/0310134 (es)
|
| prop-es:author1Link
|
- Daniel Kleitman (es)
- Daniel Kleitman (es)
|
| prop-es:author2Link
|
- Michael Saks (es)
- Peter van Emde Boas (es)
- Subhash Khot (es)
- Michael Saks (es)
- Peter van Emde Boas (es)
- Subhash Khot (es)
|
| prop-es:author3Link
|
- Mario Szegedy (es)
- Hendrik Lenstra (es)
- Oded Schramm (es)
- Mario Szegedy (es)
- Hendrik Lenstra (es)
- Oded Schramm (es)
|
| prop-es:authorlink
|
- Avi Wigderson (es)
- Ron Rivest (es)
- Andrew Yao (es)
- Andris Ambainis (es)
- Arnold L. Rosenberg (es)
- Michele Mosca (es)
- Richard Cleve (es)
- Avi Wigderson (es)
- Ron Rivest (es)
- Andrew Yao (es)
- Andris Ambainis (es)
- Arnold L. Rosenberg (es)
- Michele Mosca (es)
- Richard Cleve (es)
|
| prop-es:booktitle
| |
| prop-es:chapter
|
- Computing Graph Properties by Randomized Subcube Partitions (es)
- A topological approach to evasiveness (es)
- Computing Graph Properties by Randomized Subcube Partitions (es)
- A topological approach to evasiveness (es)
|
| prop-es:contribution
|
- Every decision tree has an influential variable (es)
- Lower bounds on the complexity of graph properties (es)
- Quantum algorithms for the triangle problem (es)
- Quantum query complexity of Boolean functions with small on-sets (es)
- A generalization and proof of the Aanderaa-Rosenberg conjecture (es)
- Improved Lower Bounds on the Randomized Complexity of Graph Properties (es)
- Every decision tree has an influential variable (es)
- Lower bounds on the complexity of graph properties (es)
- Quantum algorithms for the triangle problem (es)
- Quantum query complexity of Boolean functions with small on-sets (es)
- A generalization and proof of the Aanderaa-Rosenberg conjecture (es)
- Improved Lower Bounds on the Randomized Complexity of Graph Properties (es)
|
| prop-es:doi
|
- 101006 (xsd:integer)
- 101007 (xsd:integer)
- 101016 (xsd:integer)
- 101109 (xsd:integer)
- 101137 (xsd:integer)
- 101145 (xsd:integer)
|
| prop-es:fechaacceso
| |
| prop-es:fechaarchivo
| |
| prop-es:first
|
- Mario (es)
- Michael (es)
- DJ (es)
- D.J. (es)
- Jeff (es)
- Ronald (es)
- Eberhard (es)
- Dean (es)
- Valerie (es)
- Richard (es)
- Harry (es)
- Jean (es)
- Avi (es)
- Frédéric (es)
- Ryan (es)
- Dmitry (es)
- Robert (es)
- Rudy (es)
- Amit (es)
- Kazuo (es)
- P. (es)
- Michele (es)
- Péter (es)
- H.W. (es)
- Subhash (es)
- Masaki (es)
- Arnold L. (es)
- Ronald L. (es)
- Torsten (es)
- Shigeru (es)
- M.R. (es)
- Andris (es)
- Andrew Chi-Chih (es)
- Ehud (es)
- Frank H. (es)
- Hans Dietmar (es)
- Harumichi (es)
- Miklos (es)
- Oded (es)
- Rocco A. (es)
- Seiichiro (es)
- Yaoyun (es)
- Mario (es)
- Michael (es)
- DJ (es)
- D.J. (es)
- Jeff (es)
- Ronald (es)
- Eberhard (es)
- Dean (es)
- Valerie (es)
- Richard (es)
- Harry (es)
- Jean (es)
- Avi (es)
- Frédéric (es)
- Ryan (es)
- Dmitry (es)
- Robert (es)
- Rudy (es)
- Amit (es)
- Kazuo (es)
- P. (es)
- Michele (es)
- Péter (es)
- H.W. (es)
- Subhash (es)
- Masaki (es)
- Arnold L. (es)
- Ronald L. (es)
- Torsten (es)
- Shigeru (es)
- M.R. (es)
- Andris (es)
- Andrew Chi-Chih (es)
- Ehud (es)
- Frank H. (es)
- Hans Dietmar (es)
- Harumichi (es)
- Miklos (es)
- Oded (es)
- Rocco A. (es)
- Seiichiro (es)
- Yaoyun (es)
|
| prop-es:isbn
|
- 0 (xsd:integer)
- 978 (xsd:integer)
|
| prop-es:issn
| |
| prop-es:issue
|
- 1 (xsd:integer)
- 2 (xsd:integer)
- 3 (xsd:integer)
- 4 (xsd:integer)
- 6 (xsd:integer)
|
| prop-es:journal
| |
| prop-es:last
|
- Best (es)
- Tani (es)
- O'Donnell (es)
- Kozlov (es)
- Sturtevant (es)
- Schramm (es)
- Kahn (es)
- Lutz (es)
- King (es)
- Mosca (es)
- Raymond (es)
- Wigderson (es)
- Yao (es)
- Khot (es)
- Vuillemin (es)
- Lenstra (es)
- Rosenberg (es)
- Hajnal (es)
- Szegedy (es)
- Nishimura (es)
- Saks (es)
- Kwiatkowski (es)
- Beals (es)
- Shi (es)
- Nakanishi (es)
- Rivest (es)
- Ambainis (es)
- Buhrman (es)
- Chakrabarti (es)
- Cleve (es)
- Friedgut (es)
- Gröger (es)
- Iwama (es)
- Kleitman (es)
- Korneffel (es)
- Magniez (es)
- Santha (es)
- Scheidweiler (es)
- Servedio (es)
- Triesch (es)
- Yamashita (es)
- de Wolf (es)
- van Emde Boas (es)
- Best (es)
- Tani (es)
- O'Donnell (es)
- Kozlov (es)
- Sturtevant (es)
- Schramm (es)
- Kahn (es)
- Lutz (es)
- King (es)
- Mosca (es)
- Raymond (es)
- Wigderson (es)
- Yao (es)
- Khot (es)
- Vuillemin (es)
- Lenstra (es)
- Rosenberg (es)
- Hajnal (es)
- Szegedy (es)
- Nishimura (es)
- Saks (es)
- Kwiatkowski (es)
- Beals (es)
- Shi (es)
- Nakanishi (es)
- Rivest (es)
- Ambainis (es)
- Buhrman (es)
- Chakrabarti (es)
- Cleve (es)
- Friedgut (es)
- Gröger (es)
- Iwama (es)
- Kleitman (es)
- Korneffel (es)
- Magniez (es)
- Santha (es)
- Scheidweiler (es)
- Servedio (es)
- Triesch (es)
- Yamashita (es)
- de Wolf (es)
- van Emde Boas (es)
|
| prop-es:location
|
- Vancouver, British Columbia (es)
- Chicago, Illinois, United States (es)
- Albuquerque, New Mexico, United States (es)
- Gold Coast, Australia (es)
- Los Alamitos, CA, USA (es)
- Vancouver, British Columbia (es)
- Chicago, Illinois, United States (es)
- Albuquerque, New Mexico, United States (es)
- Gold Coast, Australia (es)
- Los Alamitos, CA, USA (es)
|
| prop-es:number
| |
| prop-es:page
| |
| prop-es:pages
|
- 6 (xsd:integer)
- 15 (xsd:integer)
- 31 (xsd:integer)
- 85 (xsd:integer)
- 110 (xsd:integer)
- 119 (xsd:integer)
- 131 (xsd:integer)
- 257 (xsd:integer)
- 259 (xsd:integer)
- 267 (xsd:integer)
- 285 (xsd:integer)
- 468 (xsd:integer)
- 517 (xsd:integer)
- 735 (xsd:integer)
- 778 (xsd:integer)
- 866 (xsd:integer)
- 907 (xsd:integer)
- 1109 (xsd:integer)
|
| prop-es:publisher
| |
| prop-es:series
|
- Lecture Notes in Computer Science (es)
- Report ZW 30/74 (es)
- Lecture Notes in Computer Science (es)
- Report ZW 30/74 (es)
|
| prop-es:title
|
- 24 (xsd:integer)
- dbpedia-es:Symposium_on_Foundations_of_Computer_Science
- dbpedia-es:Symposium_on_Theory_of_Computing
- An Ω lower bound on the randomized complexity of graph properties (es)
- On the recognition complexity of some graph properties (es)
- Evasiveness of subgraph containment and related properties (es)
- Combinatorial Algebraic Topology (es)
- Monotone bipartite graph properties are evasive (es)
- Quantum lower bounds by polynomials (es)
- Some results related to the evasiveness conjecture (es)
- Proceedings of the 19th International Symposium on Algorithms and Computation (es)
- On the time required to recognize properties of graphs: a problem (es)
- Further results on the Aanderaa-Rosenberg conjecture (es)
- An asymptotic bound for the complexity of monotone graph properties (es)
- Randomization and Approximation Techniques in Computer Science (es)
- Proceedings of the 28th International Colloquium on Automata, Languages and Programming (es)
- A Lower Bound for the Complexity of Monotone Graph Properties (es)
- On the randomized complexity of monotone graph properties (es)
- Lower bounds to randomized algorithms for graph properties (es)
- Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (es)
- A sharpened version of the Aanderaa-Rosenberg conjecture (es)
|
| prop-es:url
| |
| prop-es:urlarchivo
| |
| prop-es:volume
|
- 5 (xsd:integer)
- 10 (xsd:integer)
- 11 (xsd:integer)
- 16 (xsd:integer)
- 17 (xsd:integer)
- 27 (xsd:integer)
- 28 (xsd:integer)
- 30 (xsd:integer)
- 31 (xsd:integer)
- 42 (xsd:integer)
- 48 (xsd:integer)
- 81 (xsd:integer)
- 2076 (xsd:integer)
- 2483 (xsd:integer)
- 5369 (xsd:integer)
|
| prop-es:year
|
- 1973 (xsd:integer)
- 1974 (xsd:integer)
- 1975 (xsd:integer)
- 1980 (xsd:integer)
- 1983 (xsd:integer)
- 1988 (xsd:integer)
- 1991 (xsd:integer)
- 1992 (xsd:integer)
- 1996 (xsd:integer)
- 2001 (xsd:integer)
- 2002 (xsd:integer)
- 2005 (xsd:integer)
- 2008 (xsd:integer)
- 2010 (xsd:integer)
- 2013 (xsd:integer)
|
| dct:subject
| |
| 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 (es)
- 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)
|
| rdfs:label
|
- Conjetura de Aanderaa-Karp-Rosenberg (es)
- Conjetura de Aanderaa-Karp-Rosenberg (es)
|
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is foaf:primaryTopic
of | |
