Théorème de Ladner généralisé

45

Le théorème de Ladner stipule que si P ≠ NP, il existe une infinie hiérarchie de classes de complexité contenant strictement P et strictement contenu dans NP. La preuve utilise l'intégralité de la SAT sous plusieurs réductions de NP. La hiérarchie contient des classes de complexité construites selon une sorte de diagonalisation, chacune contenant une langue dans laquelle les langues des classes inférieures ne sont pas réductibles à plusieurs.

Cela motive ma question:

Soit C une classe de complexité et D est une classe de complexité qui contient strictement C. Si D contient des langages complets pour une notion de réduction, existe-t-il une hiérarchie infinie de classes de complexité entre C et D, en ce qui concerne le réduction?

Plus précisément, je voudrais savoir s’il existe des résultats connus pour D = P et C = LOGCFL ou C = NC , pour une notion appropriée de réduction.


L'article de Ladner inclut déjà le théorème 7 pour les classes C délimitées par l'espace, comme Kaveh l'a souligné dans une réponse. Dans sa forme la plus forte, on peut lire: si NL ≠ NP, il existe une séquence infinie de langages entre NL et NP, de dureté strictement croissante. Ceci est légèrement plus général que la version habituelle (théorème 1), qui dépend de P ≠ NP. Cependant, le document de Ladner considère uniquement D = NP.

András Salamon
la source
1
On peut d’abord poser la question en se concentrant sur des classes que nous savons déjà différentes. Par exemple, existe-t-il une hiérarchie infinie entre AC et AC [6] en ce qui concerne les projections? Cela ressemble à une question difficile! :-)000
Michaël Cadilhac
Voir aussi cstheory.stackexchange.com/questions/52/… pour une question sur l'intervalle entre P et NP.
András Salamon

Réponses:

33

La réponse à votre question est "oui" pour une grande variété de classes et de réductions, y compris les réductions d'espace log et les classes que vous avez mentionnées, comme le prouvent ces documents:

H. Vollmer. La technique du gap-language revisitée . Logique informatique, notes de cours en informatique vol. 533, pages 389-399, 1990.

K. Regan et H. Vollmer. Gap-languages ​​et classes de complexité log-time . Informatique théorique, 188 (1-2): 101-116, 1997.

(Vous pouvez télécharger les fichiers postscript gzippés de ces documents ici .)

Les preuves suivent le principe de base de l'extension par Uwe Schöning du théorème de Ladner:

Uwe Schöning. Une approche uniforme pour obtenir des ensembles diagonaux dans les classes de complexité . Informatique théorique 18 (1): 95-103, 1982.

La preuve de Schöning a toujours été ma preuve préférée du théorème de Ladner - il est à la fois simple et général.

John Watrous
la source
et qu'en est-il des cours de promesse?
Marcos Villagra
12

Il est très probable que vous puissiez accomplir cela dans un contexte générique. Il est presque certain qu'un tel résultat a déjà été prouvé dans un contexte générique, mais les références m'échappent pour le moment. Alors, voici un argument à partir de zéro.

L'écriture sur http://oldblog.computationalcomplexity.org/media/ladner.pdf a deux preuves du théorème de Ladner. La deuxième preuve, de Russell Impagliazzo, produit un langage de la forme { } où code une formule satisfaisable et est une fonction calculable en fonction du temps polynomial particulière. En remplissant simplement SAT avec le nombre approprié de , vous pouvez obtenir des ensembles "NP-intermediaires". Le remplissage est effectué pour "diagonaliser" toutes les réductions de temps polynomiales possibles, de sorte qu'aucune réduction de temps polynomiale de SAT à ne fonctionne (en supposant queL1x01f(|x|)xf1L1PNP). Pour prouver qu'il existe une infinité de degrés de dureté, on devrait pouvoir substituer à la place de SAT dans l'argument ci-dessus et répéter l'argument pour { }. Répéter avec { }.L1L2=x01f(|x|)|xL1Li=x01f(|x|)|xLi1

Il semble clair qu'une telle preuve peut être généralisée aux classes et , où (1) est correctement contenu dans , (2) a un langage complet sous -réductions, (3) la liste de toutes les rductions peuvent être énumérés de manière récursive, et (4) la fonction est calculable en . La dernière exigence peut-être inquiétante est la dernière, mais si vous regardez la définition de dans le lien, il semble très facile à calculer, pour les classes plus raisonnables que je puisse imaginer.D C D D C C f C f CCDCDDCCfCfC

Ryan Williams
la source
8

Je pense que la réponse est positive pour et la version uniforme de . La preuve de Ladner n'utilise pas grand chose d'autre que ce que vous avez dit et le fait que la classe la plus petite est représentée de manière récursive et devrait fonctionner avec des modifications mineures, mais je n'ai pas vérifié les détails, jetez un coup d'œil à l'écriture de Lance ici .N CC=LNC


Mise à jour

Vérifiez le papier de Ladner sur la structure de la réductibilité du temps polynomial

Voici l’abrégé: Deux notions de la réductibilité du temps polynomial, désignées ici par et , ont été définies par Cook et Karp, respectivement. La propriété abstraite de ces deux relations sur le domaine des ensembles calculables est étudiée. Les deux relations se révèlent denses et avoir un minimum de paires. En outre, il existe une séquence strictement ascendante avec une paire minimale de bornes supérieures à la séquence. Notre méthode de démonstration de la densité donne le résultat suivant: si certains membres de ne sont pas polynomiaux complets.P m P N P N P - PTPmPPNPNPP

THEOREME 1. Si B est calculable et non dans alors il existe un calculable tel que , et .PAAPAmPBBTPA

Voir également la section 6 qui traite des généralisations:

THEOREME 5. Si est une classe de temps puis et sont des relations réflexive et transitive et Théorèmes 1-4 avec prise remplacé par .C mC T P CCmCTCPC

THEOREME 7. Si est une classe spatiale puis et sont des relations réflexive et transitive et Théorèmes 1-4 avec prise remplacé par .C mC T P CCmCTCPC

Les termes classe de temps et classe d’ espace sont définis dans le document.

Kaveh
la source
A la façon dont j'ai compris les preuves Ladner et Impagliazzo, elles semblaient utiliser certains ingrédients spécifiques aux NP, SAT et plusieurs réductions de temps polynomial. Ma question vise précisément à savoir si ces ingrédients peuvent être utilisés de manière plus générale.
András Salamon
@ András Salamon: Non, en réalité, la preuve originale de Ladner n'utilise aucun fait à propos de SAT, à moins qu'il ne soit calculable (voir le théorème 1 ci-dessus). Dans la section 6, il discute des propriétés requises pour qu'une réduction fonctionne pour ses théorèmes. Je pense que est une classe d'espace. L
Kaveh
Je pense que ce théorème peut aussi être généralisé à des classes de circuits uniformes, de sorte que le théorème 1 fonctionne également pour (je n'ai pas vérifié les détails, je l'ajouterai à l'article quand je trouverai ou trouverai une référence), mais je ne le ferai pas. t pense que cela peut être généralisé aux versions non uniformes car la preuve utilise le fait que la classe de complexité est représentée de manière récursive. Il serait intéressant de savoir si le théorème 1 est également valable pour (version uniforme), ce qui répondrait au commentaire de Michaël Cadilhac mentionné dans le post. C = A C 0C=NCC=AC0
Kaveh
5

J'ai posé une question similaire à Peter Shor à Mathoverflow ici . Selon lui, il n'est pas au courant d'un tel résultat.

En outre, Ryan Williams a dit quelque chose de drôle à propos du théorème de Ladner mais je ne trouve pas le lien. Cela ressemble à ceci: "La démonstration du théorème de Ladner est une procédure ressemblant à un zombie dans laquelle vous prenez la tête et le torse d'un problème NP-complet, puis cousez les bras et les jambes d'un algorithme de temps polynomial". Il est plutôt moyen non naturel de définir une langue NP-intermédiaire, en supposant .NPP

J'y ai aussi pensé, et vous pouvez peut-être utiliser la procédure de Ryan ressemblant à un zombie comme ceci: Soit un ensemble complet pour , et laissez . Ensuite, vous pouvez utiliser les deux approches de l'épreuve sur en soufflant des trous ou en les rembourrant.Σ p i B Σ p i - 1 BAipBi1pB

Un autre problème intéressant consiste à envisager une généralisation de Ladner aux versions de promesse de classes sémantiques, telles que promiseBPP, promiseMA, etc.

Marcos Villagra
la source
J'ai oublié de mentionner que cela ne concerne que le PH bien sûr, et cela semble être une approche plus plausible que de prendre n'importe quelle classe de complexité.
Marcos Villagra
5
Lien: mathoverflow.net/questions/9221/…
Ryan Williams
3
Je pense que le point clé ici est que le théorème 1 dans l'article de Ladner a besoin d'une représentation récursive de car il s'agit d'une preuve de diagonalisation. Les et sont des classes sémantiques et, autant que je sache, nous ne savons pas si elles sont représentées de manière récursive. D'autre part, l'uniforme est une classe syntaxique et est représentée de manière récursive. B P P M A N CCBPPMANC
Kaveh
oui, l'énumération des machines des classes sémantiques n'est pas récursive. Mais les versions de promesses de classes sémantiques (promiseBPP, promiseMA, ...) sont vraiment sintactiques.
Marcos Villagra