La diagonalisation capture-t-elle l'essence de la séparation des classes?

11

Je ne me souviens pas d'avoir vu une séparation de classes non basée sur des résultats de diagonalisation et de relativisation. La diagonalisation pourrait toujours être utilisée pour séparer les classes connues restantes, car des arguments non relativisants pourraient toujours être utilisés dans la conclusion de la diagonalisation ou dans la construction de la machine de Turing diagonalisée. Voici quelques questions connexes:

Existe-t-il des preuves de séparation de classes non basées sur la diagonalisation?

Et si oui

Pouvons-nous trouver un mécanisme d'auto-référence derrière eux?

Plus loin,

chaque séparation de classes a-t-elle une preuve «canonique naturelle» (dans un sens informel)?

Si c'est le cas, nous devrions essayer de trouver des arguments non relativisants, plutôt que d'autres schémas de preuve pour les questions ouvertes.

Chaque épreuve non diagonale peut-elle être réécrite en une diagonale?

Ludovic Patey
la source
J'ai édité la question pour essayer de la rendre plus facile à lire. Toutes mes excuses si j'ai modifié votre intention.
András Salamon
@ András Merci pour votre édition. Je ne suis souvent pas clair. Il y a une altération: je voulais dire que la diagonalisation n'a pas échoué car à l'intérieur, nous pouvons utiliser des arguments non relativisants. Je pense que la relativisation et la diagonalisation sont orthogonales. Et je ne pense pas que les preuves qui n'utilisent pas la diagonalisation utiliseraient un mécanisme d'auto-référence profond, mais seulement que dans une compréhension profonde de la preuve, nous pourrions découvrir un mécanisme d'auto-référence non profond ^^. Je vais rééditer ces points particuliers.
Ludovic Patey

Réponses:

15

Cela dépend de la façon dont vous formalisez la diagonalisation. Kozen a un papier qui montre que toute séparation de classe de complexité doit être une preuve de diagonalisation.

Lance Fortnow
la source
+1 Je pense avoir lu ceci dans votre blog et j'attendais votre réponse :)
Mohammad Al-Turkistany
5

Puisque la diagonalisation relativise, tout résultat de complexité impliquant des relativisations contradictoires ne peut pas être basé sur la diagonalisation. Citant Arora-Barak :

OO{0,1}

PNPPNP

PPHIP

MS Dousti
la source
2
Notez que Baker, Gill et Solovay n'ont pas dit que la diagonalisation ne pouvait pas fonctionner, mais ont fait une déclaration plus nuancée "Il semble peu probable que les méthodes de diagonalisation ordinaires soient adéquates".
András Salamon
@Sadeq Je ne suis pas d'accord pour dire que la diagonalisation se relativise. Par exemple, vous pouvez définir une machine diagonale basée sur une propriété prenant en compte la propriété de localité de calcul, qui ne se relativise pas.
Ludovic Patey
L'algèbre n'est pas une technique, mais plutôt un concept similaire à la relativisation. Je suppose que vous voulez plutôt dire l'arithmétisation. Et quel est le lien avec les preuves naturelles?
Kristoffer Arnsfelt Hansen
1
@Sadeq: BGS permettait clairement une définition plus inclusive de la diagonalisation que Arora-Barak ne semble vouloir. Si un théoricien des ensembles comme Robert Solovay pense qu'il pourrait y avoir d'autres notions de diagonalisation qui ne se relativisent pas, alors nous devrions peut-être laisser cette possibilité ouverte. Remarque page 75 d'A&B ne rejette pas la possibilité qu'une sorte de diagonalisation utilise un fait non relativisant sur les machines de Turing; le manuscrit Arora-Impagliazzo-Vazirani encore inédit indique qu'il y a des problèmes assez subtils impliqués. cseweb.ucsd.edu/~russell/ias.ps
András Salamon
1
Il y a un débat à ce sujet: voir par exemple la réponse de Fortnow au document AIV: people.cs.uchicago.edu/~fortnow/papers/relative.pdf
Suresh Venkat
5

Pour ajouter à la réponse de Fortnow, poursuivant le travail de Kozen, Nash, Impagliazzo et Remmel ont formalisé une notion de forte diagonalisation et ont donné des preuves qu'elle ne relativise pas. Pour répondre partiellement à votre première question, leurs résultats montrent que certaines preuves de séparation de classe ne peuvent pas être basées sur une forte diagonalisation. Voici le résumé:

Nous définissons et étudions une diagonalisation forte et la comparons à une diagonalisation faible, implicite dans [7]. Le résultat de Kozen dans [7] montre que pratiquement chaque séparation peut être refondue en diagonalisation faible. Nous montrons qu'il existe des classes de langues qui ne peuvent pas être séparées par une forte diagonalisation et apportons la preuve qu'une forte diagonalisation ne se relativise pas. Nous définissons également deux types de diagonalisation indirecte et étudions leur puissance.

Puisque nous définissons une forte diagonalisation en termes de langages universels, nous étudions leur complexité. Nous distinguons et comparons les langages universels faibles et stricts. Enfin, nous analysons certaines variantes apparemment plus faibles des langages universels, que nous appelons langages pseudo-universels, et montrons que dans des conditions de fermeture faibles, ils produisent facilement des langages universels.

1-Nash, A., Impagliazzo, R., Remmel; J. «Les langages universels et le pouvoir de la diagonalisation». 18e conférence annuelle de l'IEEE sur la complexité informatique (CCC'03), p. 337, 2003.

Mohammad Al-Turkistany
la source
5

Existe-t-il des preuves de séparation de classes non basées sur la diagonalisation?

Oui, il y en a, mais pas pour les classes de complexité uniformes. Nous n'avons pas d'argument pour exclure de telles preuves, mais jusqu'à présent, toutes les séparations entre les classes de complexité uniformes semblent utiliser la diagonalisation à un certain endroit.

Pouvons-nous trouver un mécanisme d'auto-référence derrière eux?

Je ne pense pas que les séparations de classes de complexité non uniformes puissent être transformées en arguments "d'auto-référence" car ce ne sont pas des classes uniformes et ne peuvent pas être énumérées, et pour un argument d'auto-référence, nous devons énumérer les membres de la classe.

chaque séparation de classes a-t-elle une preuve «canonique naturelle» (dans un sens informel)?

Cela dépend de ce que vous entendez par «canonique». AFAIK, il n'y a pas de consensus sur les réponses à la question "quand deux preuves sont identiques par essence?".

Si c'est le cas, nous devrions essayer de trouver des arguments non relativisants, plutôt que d'autres schémas de preuve pour les questions ouvertes. Chaque épreuve non diagonale peut-elle être réécrite en une diagonale?

Comme d'autres l'ont souligné, la réponse dépend de ce que vous entendez par diagonalisation. Dans le sens plus général (l'article de Kozen lié par Lance), la réponse est oui pour deux "classes de complexité" différentes (telles que définies dans l'article de Kozen). Vous pouvez transformer l'argument en argument de "diagonalisation". Mais:

  1. cela ne s'applique pas aux classes de complexité qui ne satisfont pas aux exigences énoncées dans l'article de Kozen (c'est-à-dire qu'il ne s'agit pas de "classes de complexité" de Kozen).
  2. PPSpace
  3. l'important est que plus une méthode est générale, plus ses applications sont limitées (si elle est utilisée par elle-même) car la méthode a besoin de fonctionner pour plus de cas et c'est une restriction sur la méthode, on ne peut pas utiliser le spécifique les informations que nous avons sur le problème si elles ne sont pas partagées ou ne peuvent pas être remplacées par quelque chose de similaire pour d'autres problèmes que nous voulons leur appliquer.
  4. Nous pouvons transformer les arguments de séparation en arguments de "diagonalisation" (compte tenu de la restriction que j'ai mentionnée ci-dessus), mais le fait que "la fonction de diagonalisation sépare vraiment les classes" lui-même a besoin d'une preuve. L'article de Kozen montre qu'il existe une fonction de diagonalisation si les classes sont différentes, mais comment savoir qu'une fonction donnée est vraiment diagonalisante? Nous avons besoin d'une preuve! Et le papier (AFAIU) ne nous donne aucune idée sur la façon de trouver ces preuves. Si nous avons un argument de séparation, nous pouvons le transformer en preuve de diagonalisation, mais ce n'est qu'aprèsavoir une preuve. La preuve d'origine fera partie de la nouvelle preuve de diagonalisation, elle montrera que la fonction est vraiment diagonalisante. (Et dans un sens, la preuve de diagonalisation construite à partir du papier de Kozen ne sera pas "canonique" car elle dépendra complètement de l'argument d'origine.)
Kaveh
la source
Je devrais faire plus attention à votre deuxième question (pouvons-nous trouver un mécanisme d'auto-référence derrière eux?) Et à la non-uniformité. Je pense que vous devez être plus précis sur ce que vous entendez par "un mécanisme d'auto-référence". Le mot "auto-référence" est l'un des mots qui est beaucoup utilisé à mauvais escient (en particulier dans les travaux philosophiques), donc nous devons être prudents. Le mécanisme habituel d'auto-référence (au sens de Godel, voir également l'ouvrage de R. Smullyan "Diagonalization and Self-Reference", 1994) nécessite d'énumérer les objets (ici les MT) de la plus petite classe de la langue. Mais il y en a d'autres qui utilisent aussi
Kaveh
utilisez le mot «auto-référence». EgK Mulmuley l'utilise dans le cadre non uniforme de son GCT dans ce qu'il appelle le "paradoxe d'auto-référence". Mais il est difficile de voir pour moi si c'est ce à quoi vous pensez lorsque vous utilisez le "mécanisme d'auto-référence".
Kaveh