La conjecture des jeux uniques de Subhash Khot est l'un des domaines de recherche actifs en théorie de la complexité. Quelles preuves en avons-nous? Quelles preuves avons-nous contre cela?
Il existe de nombreux résultats d'inapproximabilité qui reposent sur la conjecture unique des jeux. Par exemple, En supposant la conjecture de jeux unique, il est difficile NP d'approximer le problème de coupe maximale dans un facteur R pour toute constante R > R GW . (Ici, R GW = 0,878… est le...
Comment concevriez-vous une image pour illustrer la conjecture des jeux uniques? Ceci est pour une présentation "Current Events" sur des jeux uniques lors de la prochaine réunion conjointe AMS et pour le livret qui sera produit. Des exemples du type d'illustrations produites dans le passé...
comment montrer la relation entre "Conjecture de jeux uniques" et "Théorème PCP"? comment expliquer que "la conjecture des jeux uniques" est une forme plus forte de "théorème
Contexte : Dans le document UGC original de Subhash Khot ( PDF ), il prouve la dureté UG de décider si une instance CSP donnée avec des contraintes toutes de la forme Pas-tout-égal (a, b, c) sur un alphabet ternaire admet une affectation satisfaisante 1 - des contraintes ou s'il n'y a pas...
J'étudie la Conjecture Unique Games et la fameuse réduction à Max-Cut de Khot et al. À partir de leur article et ailleurs sur Internet, la plupart des auteurs utilisent (ce qui pour moi est) une équivalence implicite entre la réduction MAX-CUT et la construction de tests particuliers pour les codes...