Des preuves probabilistes vérifiables
Je connais pas mal de résultats qui utilisent le théorème PCP (principalement dans l'approximation d'algorithmes), mais je n'ai jamais trouvé d'explication claire du théorème PCP (c'est-à-dire que ).NP=PCP(O(log(n)),O(1))NP=PCP(O(log(n)),O(1))\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1)) Quels sont...
Supposons que et G 2 soient deux graphes non dirigés sur l'ensemble de sommets { 1 , … , n } . Les graphiques sont isomorphes si et seulement s'il y a une permutation Π de telle sorte que G 1 = Π ( G 2 ) , ou plus formellement, s'il y a une permutation Π de telle sorte que ( i , j ) est une arête...
Une application importante du théorème PCP est qu'il donne des résultats de type "dureté d'approximation". Dans certains cas relativement simples, on peut prouver une telle dureté sans PCP. Existe-t-il toutefois des cas où la dureté du résultat de l'approximation a d'abord été prouvée à l'aide du...
Le théorème PCP indique qu'il n'y a pas d'algorithme de temps polynomial pour MAX 3SAT pour trouver une affectation satisfaisant 7/8 clauses d'une formule 3SAT satisfaisante à moins que .P = N P7 / huit + εsept/8+ϵ7/8+ \epsilonP= NPP=NPP = NP Il existe un algorithme de temps polynomial trivial qui...
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
Le problème de maintenance des commandes (ou «maintien de l'ordre dans une liste») est de supporter les opérations: singleton: crée une liste avec un élément, lui renvoie un pointeur insertAfter: donné un pointeur sur un élément, insère un nouvel élément après, renvoyant un pointeur sur le nouvel...
Le système de preuve probabiliste est communément appelé une restriction de , où Arthur ne peut utiliser que bits aléatoires et ne peut examiner que bits du certificat de preuve envoyé par Merlin (voir, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).M A f ( n ) g ( n )PCP[ f( n ) , g(...
Le théorème de prétention parallèle de Raz est un résultat important dans le PCP, l'inapproximation, etc. Le théorème est fomalisé comme suit. Un jeu , où S , T , A , B sont des ensembles finis, π est une distribution sur S × T et un prédicat V : S × T × A × B → { 0 , 1 } . Définir la valeur du jeu...
Une formulation équivalente du théorème PCP est: Pour Max 3-SAT, il est -hard de faire la distinction entre les formules satisfaisables et les formules où au plus r -fraction des clauses sont satisfaisables (pour certains r < 1 ).NPNPNPrrrr<1r<1r\lt 1 Existe-t-il un théorème de dichotomie...
Je lis la preuve d' ici et je suis tombé sur un problème technique (pourtant crucial). Je sais que c'est assez spécifique et le contexte est problématique, mais je n'ai pas pu le comprendre moi-même. Aux pages 51 et 55, après avoir présenté les vérificateurs "standard", ils se tournent pour...
Ce qui suit peut sembler stupide (et cela reflète probablement ma mauvaise compréhension - alors soyez patient avec moi) J'avais une requête sur le théorème du PCP. Nous savons qu'après les trois premières étapes, à savoir. Réduction de degré, expansion et amplification de l'écart, nous avons un...
Dans la plupart des systèmes de preuve probabilistes (théorème PCP, par exemple), les probabilités d'erreur sont généralement définies du côté des faux positifs, c'est-à-dire qu'une définition typique pourrait ressembler à: si alors le vérificateur accepte toujours, mais dans les autres cas, la...
Le théorème du PCP déclare que chaque problème de décision dans NP a des preuves probabilistes vérifiables (ou de manière équivalente, qu'il existe un système de preuve complet et quasi-sain pour les théorèmes dans NP utilisant une complexité de requête constante et logarithmiquement de nombreux...
Le livre d'Arora et Barak contient des notes de chapitre sur PCP Nous notons que la stratégie générale de Dinur rappelle quelque peu la construction en zig-zag des graphiques d'extension et l'algorithme déterministe de l'espace de journalisation de Reingold pour la connectivité non dirigée décrit...
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...
Quelles sont les limites supérieures asymptotiques les plus connues sur les tailles des preuves vérifiables de manière probabiliste? Idéalement, je recherche une enquête contemporaine sur cette large question, mais s'il n'y en a pas, je suis particulièrement intéressé par l'inapproximabilité du...