| dbo: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 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 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 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 , 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. (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 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)
- 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é satisfaisant cette conjecture est dite évasive. (fr)
- Гипотеза Аандераа — Карпа — Розенберга (известная также как гипотеза Аандераа — Розенберга или гипотеза трудности) — это группа связанных гипотез о числе вопросов в форме «Имеется ли ребро между вершиной u и вершиной v?», на которые следует ответить, чтобы определить, обладает или нет неориентированный граф определённым свойством (инвариантом), таким как планарность или двудольность. Гипотеза названа именами норвежского математика Стола Аандераа и американских учёных Ричарда М. Карпа и Арнольда Л. Розенберга. Согласно гипотезе, для широкого класса инвариантов никакой алгоритм не может гарантировать, что алгоритм может опустить какой-либо запрос — любой алгоритм определения, обладает ли граф свойством, неважно, насколько умён этот алгоритм, он должен проверить каждую пару вершин, прежде чем дать ответ. Свойство, удовлетворяющее гипотезе, называется . Более точно, гипотеза Аандераа — Розенберга утверждает, что любой детерминированный алгоритм должен проверить по меньшей мере фиксированную долю всех возможных пар вершин, чтобы определить в любое нетривиальное монотонное свойство графа. В этом контексте свойство монотонно, если оно остаётся верным при добавлении рёбер (так что свойство планарности монотонным не является, а вот непланарность монотонна). Более строгая версия этой гипотезы, называемая гипотезой трудности или гипотезой Аандераа — Карпа — Розенберга, утверждает, что необходимо в точности проверок. Были сформулированы и изучались версии проблемы для вероятностных и квантовых алгоритмов. Детерминированную гипотезу Аандераа — Розенберга доказали Ривест и Виллемин, но более сильная гипотеза гипотеза Аандераа — Карпа — Розенберга остаётся недоказанной. Кроме того, существует большая разница между нижней границей и лучшей доказанной нижней границей для вероятностной и квантовой сложности по количеству запросов. (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)
|
