en termes de

15

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(n)]MUNEF(n)g(n)

Cependant, en 1990, Babai, Fortnow et Lund ont prouvé que , ce n'est donc pas exactement une restriction. Quels sont les paramètres ( ) pour lesquels ?PCP[poly(n),poly(n)]=NEXPF(n),g(n)PCP[F(n),g(n)]=MUNE

Belle
la source

Réponses:

18

Si vous souhaitez reformuler la définition de MA en termes de PCP, vous avez besoin d'un autre paramètre pour PCP, à savoir la longueur d'épreuve. MA est clairement le même que PCP avec l'aléa polynomial, les requêtes polynomiales et les preuves de longueur polynomiale. Habituellement, la longueur de la preuve dans PCP n'est pas limitée (c'est-à-dire qu'elle n'est limitée qu'implicitement par le hasard et les requêtes), mais cela est insuffisant pour reformuler la définition de MA.

Si vous recherchez une caractérisation de la forme MA = PCP ( q ( n ), r ( n )), qui n'est pas seulement la reformulation de la définition de MA, alors je ne pense pas qu'une telle caractérisation soit connue.

Tsuyoshi Ito
la source
11

Dans une hypothèse de dureté, à savoir que la classe de complexité nécessite des circuits de taille exponentielle, il suffit de dérandomiser , de sorte que . En fait, la dérandomisation doit montrer que (voir Impagliazzo-Wigderson ou Sudan-Trevisan-Vadhan). Mais comme dans le vérificateur est une machine , nous pouvons le remplacer par une machine déterministe.E=TjeME(2O(n))MUNEMUNE=NPBPP=PMUNEBPP

Ainsi, modulo cette hypothèse de dureté, devrait avoir exactement la même caractérisation PCP que . La communauté de la complexité semble croire fermement que l'hypothèse de dureté est également vraie.MUNENP

Edit: Vous pouvez également consulter la thèse de maîtrise d'Andy Drucker: "Une caractérisation PCP de la ": http://eccc.hpi-web.de/report/2010/019/ .UNEM

Impagliazzo-Wigderson: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf

Soudan-Trevisan-Vadhan: http://www.cs.berkeley.edu/~luca/pubs/stv-full.ps

Henry Yuen
la source
11

Tsuyoshi Ito a répondu à la question littéralement, mais je voulais commenter la sémantique de MA et PCP et comment ils diffèrent.

MA est la version probabiliste de NP, c'est-à-dire que le vérificateur peut également utiliser des bits aléatoires poly-plusieurs.

Dans PCP, nous pouvons nous référer au "caractère aléatoire" du vérificateur, mais généralement le caractère aléatoire est logarithmique dans le temps de fonctionnement du vérificateur, c'est-à-dire que le vérificateur aurait pu essayer toutes les chaînes aléatoires possibles par lui-même. En d'autres termes, ce "caractère aléatoire" n'achète au vérificateur aucune puissance de calcul, contrairement au cas de MA.

[Alors, à quoi sert ce "hasard"? Le but du PCP est que pour la vérification probabiliste, un seul test - avec un nombre constant de requêtes à la preuve - suffit]

Addendum (à la suite du commentaire de Tsuyoshi): Dans les caractérisations PCP de NP, le temps d'exécution du vérificateur peut être rendu poly-logarithmique et, de même, dans les caractérisations de NEXP, le temps d'exécution du vérificateur est polynomial. Néanmoins, le caractère aléatoire dans les constructions PCP est généralement utilisé uniquement pour choisir un test (dans les caractérisations de NP, sur les tests poly-plusieurs et dans les caractérisations de NEXP, sur un nombre exponentiellement élevé) et non pour aider au calcul. De plus, dans MA, la preuve est de taille polynomiale, tandis que dans les caractérisations de NEXP, la preuve est de taille exponentielle.

Dana Moshkovitz
la source
Je suis d'accord que nous ne donnons au vérificateur que le caractère aléatoire logarithmique dans le théorème PCP pour NP, de sorte que ce caractère aléatoire seul n'achètera au vérificateur aucune puissance de calcul. Cependant, il semble que vous fassiez une affirmation plus générale que celle-ci en déclarant «généralement le caractère aléatoire est logarithmique dans le temps de fonctionnement du vérificateur», ce qui, je le crains, est trop général pour être vrai. Habituellement, nous ne permettons pas au vérificateur de passer du temps exponentiel même lorsque nous considérons PCP (poly, poly) = NEXP (bien que cela ne change pas cette égalité), et cela semble être un contre-exemple à votre déclaration.
Tsuyoshi Ito
1
Merci pour le suivi! Je pense que maintenant je comprends mieux ce que vous voulez dire en disant que MA et PCP utilisent le hasard différemment.
Tsuyoshi Ito