Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Unique_games_conjecture> ?p ?o. }
Showing items 1 to 39 of
39
with 100 items per page.
- Unique_games_conjecture abstract "In computational complexity theory, the Unique Games Conjecture 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 algorithmic complexity. It has broad applications in the theory of hardness of approximation. If it is true, then for many important problems it is not only too hard to get an exact solution (as postulated by the P versus NP problem), but also too hard to get a good approximation. There are important implications for 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."Some very natural, intrinsically interesting statements about things like voting and foams just popped out of studying the UGC.... Even if the UGC turns out to be false, it has inspired a lot of interesting math research.".
- Unique_games_conjecture wikiPageExternalLink UGCSurvey.pdf.
- Unique_games_conjecture wikiPageID "3000842".
- Unique_games_conjecture wikiPageRevisionID "605917427".
- Unique_games_conjecture hasPhotoCollection Unique_games_conjecture.
- Unique_games_conjecture subject Category:Computational_complexity_theory.
- Unique_games_conjecture subject Category:Computational_hardness_assumptions.
- Unique_games_conjecture subject Category:Conjectures.
- Unique_games_conjecture subject Category:Unsolved_problems_in_computer_science.
- Unique_games_conjecture type Abstraction100002137.
- Unique_games_conjecture type Attribute100024264.
- Unique_games_conjecture type Cognition100023271.
- Unique_games_conjecture type Communication100033020.
- Unique_games_conjecture type ComputationalHardnessAssumptions.
- Unique_games_conjecture type Concept105835747.
- Unique_games_conjecture type Condition113920835.
- Unique_games_conjecture type Conjectures.
- Unique_games_conjecture type Content105809192.
- Unique_games_conjecture type Difficulty114408086.
- Unique_games_conjecture type Hypothesis105888929.
- Unique_games_conjecture type Idea105833840.
- Unique_games_conjecture type Message106598915.
- Unique_games_conjecture type Postulate106753299.
- Unique_games_conjecture type Premise106753800.
- Unique_games_conjecture type Problem114410605.
- Unique_games_conjecture type Proposition106750804.
- Unique_games_conjecture type PsychologicalFeature100023100.
- Unique_games_conjecture type Speculation105891783.
- Unique_games_conjecture type State100024720.
- Unique_games_conjecture type Statement106722453.
- Unique_games_conjecture type UnsolvedProblemsInComputerScience.
- Unique_games_conjecture comment "In computational complexity theory, the Unique Games Conjecture 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 algorithmic complexity. It has broad applications in the theory of hardness of approximation.".
- Unique_games_conjecture label "Unique games conjecture".
- Unique_games_conjecture sameAs m.08jr_f.
- Unique_games_conjecture sameAs Q7886950.
- Unique_games_conjecture sameAs Q7886950.
- Unique_games_conjecture sameAs Unique_games_conjecture.
- Unique_games_conjecture wasDerivedFrom Unique_games_conjecture?oldid=605917427.
- Unique_games_conjecture isPrimaryTopicOf Unique_games_conjecture.