Pourquoi est-relativisation une barrière?

Question

Quand j'expliquais la preuve Baker-Gill-Solovay qu'il existe un oracle avec lequel nous pouvons avoir, $ \ mathsf {P} = \ mathsf {NP} $, et un oracle avec lequel nous pouvons avoir $ \ mathsf {P} \ neq \ mathsf {NP} $ à un ami, une question a été posée de savoir pourquoi ces techniques sont mal adaptées pour prouver le $ \ mathsf {P} \ neq \ mathsf {NP} $ problème, et je ne pouvais « t donner une réponse satisfaisante.

Pour mettre plus concrètement, si j'ai une approche de prouver $ \ mathsf {P} \ neq \ mathsf {NP} $ et si je pouvais construire Oracles pour faire une situation comme ci-dessus se produire, pourquoi est-il ma méthode invalide?

Toute exposition / réflexions sur ce sujet?

Answer 1

  

Pour mettre plus concrètement, si j'ai une approche de prouver P ? NP et si je pouvais construire Oracles pour faire une situation comme ci-dessus se produire, pourquoi est-il mon invalide méthode?

Notez que ce dernier « si » est pas une condition, parce que Baker, Gill et Solovay déjà construit un tel oracle. Il est juste une vérité mathématique (1), il existe un oracle par rapport auquel P = NP, et que (2), il existe un oracle par rapport auquel P ? NP.

Cela signifie que si vous avez une approche de prouver P ? NP et la même preuve seraient également se révéler un fort résultat « P ^A ? NP ^A pour tous les oracles A « , alors votre approche est vouée à l'échec, car il serait en contradiction avec (1).

En d'autres termes, il existe une différence fondamentale entre la preuve P ? NP et de prouver, par exemple le théorème de hiérarchie de temps, parce que la preuve de celle-ci utilise juste diagonalisation et est également applicable à tout monde relativisée.

Bien sûr, cela ne signifie pas qu'il n'y a pas de preuve pour P ? NP. Une telle preuve (le cas échéant) doit ne prouve pas la plus forte résultat mentionné ci-dessus. Autrement dit, une partie de la preuve doit distinguer le monde nonrelativizing des mondes relativisée arbitraires.

Answer 2

Il existe déjà de bonnes réponses, mais je voudrais ajouter quelques petits points.

Supposons que nous ayons une technique pour résoudre les problèmes, par exemple diagonalisation . Supposons que nous voulons montrer que la technique ne peut pas résoudre un problème spécifique par exemple $ \ mathsf {P} $ par rapport à $ \ mathsf {NP} $ . Comment peut-on montrer?

Avant d'aller plus loin, notez qu'une technique comme diagonalisation est pas un concept formel ici (bien que nous pouvons faire en sorte). De plus, le fait que la technique ne peut pas résoudre le problème par lui-même ne veut pas dire qu'il ne soit pas utile pour résoudre le problème, nous pourrions être en mesure de modifier et / ou le combiner avec d'autres techniques pour résoudre le problème.

Maintenant, nous allons revenir à la question. Une façon de montrer qu'une technique ne peut pas résoudre un problème spécifique est de montrer que si elle pouvait elle aussi travailler dans un cadre différent pour résoudre une autre question, et la réponse que nous aurions dans ce cas serait faux. Voilà ce qui arrive ici. Si la diagonalisation pourrait séparer $ \ mathsf {NP} $ de $ \ mathsf {P} $, alors le même argument pourrait être utilisé pour séparer $ \ mathsf {NP ^ A} $ de $ \ mathsf {P ^ A} $ pour tous $ A $. Mais nous savons qu'il ya un oracle tel que cela est faux (prendre de $ \ mathsf {PSpace} $ - problème complet comme l'oracle). Donc diagonalisation ne peut pas séparer $ \ mathsf {NP} $ de $ \ mathsf {P} $.

Le point essentiel dans cet argument est une sorte de principe de transfert :

  

nous pouvons transférer un argument de diagonalisation pour oracle sans mémoires de traduction avec les mémoires de traduction Oracles.

Il est possible ici parce que les arguments de diagonalisation sont basés sur Simulation de machines, d'ailleurs la simulation ne dépend pas des entrailles de machines, mais uniquement sur les réponses finales de ces simulations. Ce genre de diagonalisation est appelée diagonalisation simples . Dans une simulation, peu importe comment la machine fonctionne, nous prenons soin que la réponse finale de la machine. Ajout d'un oracle ne changera pas cela pour la simulation et l'argument fonctionne également dans le cadre où nous avons Oracles.

Plus formellement, on peut penser à un argument de diagonalisation en fonction d'une classe de machines (dire $ \ mathsf {P} $) aux instances montrant que la machine ne peut pas résoudre un problème (disons $ SAT $). Cette fonction est la fonction contre-diagonalisation. Un diagonalisation est simple si les contre qu'il donne ne dépendent pas de la structure interne des machines, à savoir si deux DTMs polynomiaux ont la même langue, puis le contre montrant qu'ils ne peuvent pas résoudre $ SAT $ donnée par la fonction de diagonalisation est le même.

On peut se demander si cela est une grande restriction? Pourquoi les contre-besoin de dépendre de la structure interne de la machine? Peut-on prouver les séparations à l'aide de diagonalisation qui ne peut pas être prouvée en utilisant diagonalisation simple? La réponse est oui. En fait Közen montre dans son 1978 papier « Indexation des classes subrecursive » (3 ans après résultat BGS) que si $ \ mathsf {NP} $ peut être séparé de $ \ mathsf {P} $, alors il y a un argument de diagonalisation général pour elle . Et dans la pratique, ces arguments ont été trouvés. Par exemple, Fortnow et van Melkebeek espace-temps limites inférieures pour SAT (2000) utilisent une technique appelée diagonalisation indirecte qui donne une diagonalisation non simple.

est l'affirmation selon laquelle diagonalisation ne peut pas résoudre $ \ mathsf {P} $ par rapport à $ \ mathsf {NP} $ incorrect? Eh bien, en général ce que les experts signifie par diagonalisation est ici diagonalisation simples et il y a une bonne raison pour cela.

Les arguments de diagonalisation généraux sont si généraux qu'il n'a pas vraiment de sens de les appeler une technique, vous pouvez facilement transformer un argument de séparation en un argument de diagonalisation sans beaucoup de perspicacité: Si nous avons déjà une certaine façon de séparer deux complexes les classes, nous pouvons choisir une fonction dans la plus grande classe pas dans laplus petit. Prenez une énumération des machines dans la classe plus petite. Soit $ M $ soit des machines dans l'énumération. Nous devons définir le M $ pour contre-$. Mais nous savons déjà que ne peut pas résoudre le problème, donc il existe exemple montrant cela, définir la valeur de la fonction diagonalisation à être ce cas $ M $ M $ $. Ceci est le point de vue grand-image, si vous voulez voir les détails, consultez le document de Kozen.

Estival:

• Quand les experts disent "diagonalisation ne peut pas résoudre $ \ mathsf {P} $ par rapport à $ \ mathsf {NP} $" ce qu'ils veulent dire est « simple, diagonalisation ne peut pas résoudre $ \ mathsf {P} $ par rapport à $ \ mathsf {NP} $ » et non l'ordre général.
• La diagonalisation simple raison ne peut pas séparer $ \ mathsf {NP} $ de $ \ mathsf {P} $ est qu'il transfère au cadre avec Oracles (dans la littérature, il est indiqué que « diagonalisation relativisée ») et la séparation ne pas là tenir.
• La raison pour laquelle ce transfert du cadre oracle-moins à cadre avec Oracles fonctionne est que diagonalisation simple est basée sur la simulation de la boîte noire de mémoires de traduction et il n'a pas d'importance comment les machines fonctionne, si elle a un oracle ou non.

Deux bons papiers pour en savoir plus sur diagonalisation

• document d'enquête de Lance Fortnow "Diagonalisation", 2001, et
• Russell Impagliazzo, Valentine Kabanets et le papier de Antonina Kolokolova "Une axiomatique d'approche à algébrisation", 2009. (Notez que algébrisation est une extension de diagonalisation simples .)

Answer 3

Soit $ \ mathrm {A} $ et $ \ mathrm {B} $ deux classes de complexité. Une séparation ($ \ mathrm {A} \ neq \ mathrm {B} $) ou l'effondrement ($ \ mathrm {A} = \ mathrm {B} $) est dit à relativiser si pour tous les oracles $ \ mathrm {O} $ nous avons $ \ mathrm {A} ^ \ mathrm {O} \ neq \ mathrm {B} ^ \ mathrm {O} $ ou $ \ mathrm {A} ^ \ mathrm {O} = \ mathrm {B} ^ \ mathrm {O} $ respectivement. La preuve Baker-Gill-Solovay nous dit que $ P = NP $ ou $ P \ NEQ NP $ ne relativiser.

Pourquoi est-ce un problème? Lorsque cette preuve est sorti, la plupart des techniques et des astuces que nous savions que pour séparer ou classes de complexité de l'effondrement « relativisée », en ce sens qu'ils travaillent par rapport à un oracle. Par exemple, le théorème de hiérarchie temporelle (ainsi que l'espace et les versions non déterministes de celui-ci) « relativiser »: ils prouvent les séparations des classes pour lesquelles cette relativise de séparation, et en fait, ils prouvent le résultat plus fort que la séparation tient en ce qui concerne tout oracle.

Si une technique ou astuce fonctionne indépendamment du fait que il y a un oracle présent, alors il ne peut peut-être prouver $ P = NP $ ou $ P \ NEQ NP $ par l'argument ci-dessus. Cela signifie qu'un grand nombre de trucs et techniques que nous connaissons ne fonctionnent pas sur ce problème (ou bien sur beaucoup de problèmes ouverts). Vous pouvez également l'utiliser comme une vérification de bon sens pour toute prétendue $ P \ NEQ NP preuve $: vérifier si l'idée ne tient pas en présence d'un $ \ mathrm {PSPACE} $ - oracle complet - si elle fonctionne encore, il ne va pas.