Unique games conjecture
http://dbpedia.org/resource/Unique_games_conjecture an entity of type: WikicatComputationalHardnessAssumptions
La conjecture des jeux uniques (en anglais Unique Games Conjecture) est une conjecture en théorie de la complexité, proposée par Subhash Khot en 2002. Selon cette conjecture, résoudre de manière approximative un certain problème spécifique est NP-difficile. Elle a d'importantes applications relatives à la complexité des algorithmes d'approximation ; le travail qui a été fourni autour de cette conjecture a également permis de démontrer des résultats relatifs à d'autres sujets, par exemple sur la stabilité des systèmes de vote. Subhash Khot a reçu le prix Nevanlinna en 2014 pour son travail sur cette conjecture.
rdf:langString
En teoría de la complejidad computacional, la Conjetura del Juego Único es una conjetura hecha por en 2002. La conjetura postula que el problema de determinar el valor aproximado de un determinado tipo de juego, conocido como un juego único, tiene complejidad algorítmica NP-hard. Tiene amplias aplicaciones en la teoría de la . Si esto es cierto, entonces para muchos problemas importantes no es sólo demasiado difícil conseguir una solución exacta (como postula el problema ), sino también muy difícil obtener una buena aproximación. Hay implicaciones importantes para problema de satisfacción de restricciones que surgen en una amplia variedad de disciplinas.
rdf:langString
In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP, then for many important problems it is not only impossible to get an exact solution in polynomial time (as postulated by the P versus NP problem), but also impossible to get a good polynomial-time approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.
rdf:langString
Na teoria da complexidade computacional, a Conjectura de Jogos Únicos é uma conjectura feita por Subhash Khot em 2002. A conjectura postula que o problema de determinar o valor aproximado de um determinado tipo de jogo, conhecido como um jogo único, tem complexidade algorítmica NP-difícil. Ele tem amplas aplicações na teoria da . Se isso é verdade, então para muitos problemas importantes não só é impossível obter uma solução exata em tempo polinomial (tal como postulado pelo problema P versus NP), mas também é impossível obter uma boa aproximação de tempo polinomial. Os problemas para os quais tal resultado de inaproximabilidade se mantém incluem problemas de satisfação de restrições que surgem em uma ampla variedade de disciplinas.
rdf:langString
rdf:langString
Conjetura del Juego Único
rdf:langString
Conjecture des jeux uniques
rdf:langString
Conjectura de jogos únicos
rdf:langString
Unique games conjecture
xsd:integer
3000842
xsd:integer
1118086973
rdf:langString
En teoría de la complejidad computacional, la Conjetura del Juego Único es una conjetura hecha por en 2002. La conjetura postula que el problema de determinar el valor aproximado de un determinado tipo de juego, conocido como un juego único, tiene complejidad algorítmica NP-hard. Tiene amplias aplicaciones en la teoría de la . Si esto es cierto, entonces para muchos problemas importantes no es sólo demasiado difícil conseguir una solución exacta (como postula el problema ), sino también muy difícil obtener una buena aproximación. Hay implicaciones importantes para problema de satisfacción de restricciones que surgen en una amplia variedad de disciplinas. La conjetura es inusual y el mundo académico parece acerca uniformemente dividido sobre si es cierto o no. "Algunas declaraciones muy naturales, intrínsecamente interesantes sobre cosas como la votación y espumas sólo salieron al estudiar la CJU.... Incluso si la CJU resulta ser falsa, ha inspirado una gran cantidad de interesantes investigaciones matemáticas." Ryan O’Donnell
rdf:langString
La conjecture des jeux uniques (en anglais Unique Games Conjecture) est une conjecture en théorie de la complexité, proposée par Subhash Khot en 2002. Selon cette conjecture, résoudre de manière approximative un certain problème spécifique est NP-difficile. Elle a d'importantes applications relatives à la complexité des algorithmes d'approximation ; le travail qui a été fourni autour de cette conjecture a également permis de démontrer des résultats relatifs à d'autres sujets, par exemple sur la stabilité des systèmes de vote. Subhash Khot a reçu le prix Nevanlinna en 2014 pour son travail sur cette conjecture.
rdf:langString
In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP, then for many important problems it is not only impossible to get an exact solution in polynomial time (as postulated by the P versus NP problem), but also impossible to get a good polynomial-time approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines. The conjecture is unusual in that the academic world seems about evenly divided on whether it is true or not.
rdf:langString
Na teoria da complexidade computacional, a Conjectura de Jogos Únicos é uma conjectura feita por Subhash Khot em 2002. A conjectura postula que o problema de determinar o valor aproximado de um determinado tipo de jogo, conhecido como um jogo único, tem complexidade algorítmica NP-difícil. Ele tem amplas aplicações na teoria da . Se isso é verdade, então para muitos problemas importantes não só é impossível obter uma solução exata em tempo polinomial (tal como postulado pelo problema P versus NP), mas também é impossível obter uma boa aproximação de tempo polinomial. Os problemas para os quais tal resultado de inaproximabilidade se mantém incluem problemas de satisfação de restrições que surgem em uma ampla variedade de disciplinas. A conjectura é incomum, de forma que o mundo acadêmico parece igualmente dividido sobre ela ser verdadeira ou não.
xsd:nonNegativeInteger
22766