Les résultats de la relativisation peuvent-ils être utilisés pour prouver des phrases formellement indépendantes?

12

Est-il possible de démontrer qu'une phrase doit être formellement indépendante du fait qu'elle est non relativisante? En d'autres termes, existe-t-il des exemples de phrases dans la théorie de la calculabilité / complexité où il peut être démontré à la fois a) que toutes les preuves qui résolvent la question de savoir si deux classes sont égales ou non doivent se relativiser, et b) qu'il n'y a pas de preuves relativisantes qui peut être utilisé dans une telle résolution?

Je pense que des résultats satisfaisant la partie b seraient plus faciles à trouver. Une autre façon de poser cette question est: Y a-t-il déjà eu une phrase dans la théorie de la calculabilité ou de la complexité où il peut être démontré que l'égalité ou l'inégalité doit être établie en utilisant (et seulement en utilisant) des techniques de relativisation? Un exemple de cela me serait intéressant.

Merci; une réponse à l'une ou l'autre version de cette question me serait très intéressante.

-Philippe

Philip White
la source

Réponses:

18

Il n'y a pas de questions "naturelles" de théorie de la complexité qui se soient révélées indépendantes de systèmes formels vraiment puissants, comme la théorie des ensembles ZF ou l'arithmétique Peano. (On pourrait certainement construire une telle question artificiellement, en jouant à des jeux avec des phrases de Gödel.)

D'un autre côté, oui, vous pouvez interpréter l'affirmation qu'une phrase S relativise comme signifiant que S peut être prouvé à partir d'un certain ensemble restreint d'axiomes (fondamentalement, les "axiomes de Cobham" qui caractérisent la fermeture sous des réductions de temps polynomiales). Inversement, l'existence d'oracles rendant S vrai ou faux équivaut à ce que S soit indépendant de ces axiomes particuliers. Voici l'article à lire à ce sujet, par Arora, Impagliazzo et Vazirani.

Ceci est une connexion très joli mathématiquement --- mais il est intéressant de souligner que nous n'avons des techniques (comme arithmétisation) qui vont en dehors des axiomes relativisation. Et je ne connais aucun résultat de la forme "si le problème ouvert naturel P peut être résolu du tout, alors il peut aussi être résolu de manière relativisante."

Scott Aaronson
la source
4
Je pense qu'Impagliazzo-Kabanets-Kolokolova a étendu Arora-Impagliazzo-Vazirani à l'arithmétisation dans le STOC 2009: dx.doi.org/10.1145/1536414.1536509
Joshua Grochow