Existe-t-il des techniques canoniques non relativisantes?

Dans de nombreux domaines, il existe des techniques canoniques que tous ceux qui travaillent dans le domaine devraient maîtriser. Par exemple, pour les réductions d'espace de journalisation, le "truc de bit" pour la composition consiste à ne pas construire la sortie complète de la fonction composée, mais à toujours demander de recalculer le résultat pour chaque bit de sortie, permettant de conserver les contraintes d'espace de journalisation.

Ma question concerne les techniques non relativisantes. Les théoriciens ont-ils décrit certaines opérations fondamentales non relativisantes, ou existe-t-il une astuce différente pour chaque preuve non relativisante connue?

Il n'y a vraiment qu'une seule technique «non phare» non relativisante: à savoir l' arithmétisation (la technique utilisée dans les preuves de IP = PSPACE, MIP = NEXP, PP⊄SIZE (n ^k ), MA _EXP ⊄P / poly, et plusieurs autres résultats ).

Cependant, la preuve que tous les langages NP ont des preuves de connaissance zéro de calcul (en supposant qu'il existe des fonctions unidirectionnelles), due à Goldreich, Micali et Wigderson, a utilisé une technique non relativisante différente (à savoir, les symétries du problème 3-COLORING ).

Arora, Impagliazzo et Vazirani ont soutenu que même la «vérifiabilité locale», la propriété des problèmes NP-complets utilisés dans la preuve du théorème de Cook-Levin original (ainsi que le théorème PCP), devrait compter comme une technique non relativisante ( bien que Lance Fortnow ait écrit un article soutenant le contraire). Le problème est de savoir s'il est judicieux de relativiser la classe de complexité des «problèmes vérifiables localement».

Les arguments de galets utilisés dans les résultats des années 1970 tels que TIME (n) ≠ NTIME (n) ont été présentés comme un autre exemple de technique non relativisante.

Pour en savoir plus, vous voudrez peut-être consulter mon document d'algèbre avec Wigderson , et surtout les références qu'il contient . Nous avons dû à peu près cataloguer les techniques existantes de non-relativisation afin de déterminer celles qui étaient et n'étaient pas englobées par la barrière d'algèbre.

Addendum: je viens de réaliser que j'avais oublié de mentionner l'informatique quantique basée sur la mesure (MBQC) , qui a récemment été utilisée avec grand succès par Broadbent, Fitzsimons et Kashefi pour obtenir des théorèmes de complexité quantique (tels que QMIP = MIP * et BQP = MIP avec des prouveurs BQP enchevêtrés et un vérificateur BPP) qui ne parviennent probablement pas à relativiser.