Pourquoi les égalités entre les classes de complexité se traduisent-elles vers le haut et non vers le bas?

25

Hé les gars, je comprends que l'astuce de remplissage nous permet de traduire les classes de complexité vers le haut - par exemple . Le remplissage fonctionne en "gonflant" l'entrée, en exécutant la conversion (disons de à ), ce qui donne un algorithme "magique" que vous pouvez exécuter sur l'entrée rembourrée. Bien que cela ait un sens technique, je ne peux pas avoir une bonne intuition de la façon dont cela fonctionne. Que se passe-t-il exactement ici? Existe-t-il une analogie simple avec ce qu'est le rembourrage?P=NPEXP=NEXPNPP

Peut fournir une raison de bon sens pourquoi c'est le cas?

gabgoh
la source
11
Je voudrais souligner que tous les résultats des classes de complexité ne montent pas. Par exemple, si vous avez prouvé , cela impliquerait . En général, les effondrements augmentent, tandis que les séparations diminuent. P N PEXPNEXPPNP
Robin Kothari
effectivement. En fait, cela semble être une bonne façon d'y penser, car les séparations sont plus intuitives que les effondrements.
gabgoh
2
@Robin, @gabgoh: même certains effondrements vont vers le bas, mais pas en remplissant les arguments. Voir par exemple arxiv.org/abs/cs/9910008 .
Joshua Grochow

Réponses:

30

Je pense que la meilleure façon d'obtenir l'intuition pour ce problème est de penser à ce que sont les problèmes complets pour les classes de temps exponentielles. Par exemple, les problèmes complets pour NE sont les problèmes NP-complets standard sur des entrées succinctement descriptibles, par exemple, étant donné un circuit qui décrit la matrice d'adjacence d'un graphe, le graphe est-il tricolore? Ensuite, le problème de savoir si E = NE devient équivalent à si les problèmes NP sont résolubles en temps polynomial sur les entrées succinctement descriptibles, par exemple, celles avec une petite complexité effective de Kolmogorov. Ce n'est évidemment pas plus fort que s'ils sont résolubles sur tous les intrants. Plus la limite de temps est grande, plus la complexité de Kolmogorov des entrées pertinentes est petite, donc les effondrements pour des limites de temps plus grandes sont en fait des algorithmes qui fonctionnent sur des sous-ensembles d'entrées plus petits.

Russell Impagliazzo

Russell Impagliazzo
la source
14

OK, donc votre objectif est de montrer que basant sur C L A S S 1 [ g ( n ) ] = C L A S S 2 [ h ( n ) ]CLASS1[g(f(n))]=CLASS2[h(f(n))]CLASS1[g(n)]=CLASS2[h(n)](nous ne précisons pas ce que sont exactement ces classes, nous savons juste qu'elles sont en quelque sorte paramétrées avec la taille d'entrée). Nous avons un langage , décidée par un algorithme A . Maintenant on fait un langage L en remplissant chaque mot dans x L , de sorte que sa longueur soit maintenant f ( n ) , et on voit qu'il est contenu dans C L A S S 1 [ gLCLASS1[g(f(n))]ALxLf(n) (notre nouvel algorithme A ' ignore simplement les zéros ajoutés et exécute A sur la vraie entrée courte).CLASS1[g(n)]AA

Ce que nous faisons est: nous prenons un langage de la plus grande classe et nous le remplissons, afin qu'il puisse être résolu par un algorithme plus faible nous donnant un confinement dans la classe plus petite - l'algorithme le plus faible peut le faire, car il a la même quantité de «vrai travail» pour faire comme avant, mais il a ses restrictions (en fonction de la longueur d'entrée) levées en étendant l'entrée.

Nous savons maintenant que et donc L C L A S S 2 [ h ( n ) ] (décidé par un algorithme B ). Nous aimerions aller d'ici à L C L A S S 2 [ h ( f ( n ) ) ]LCLASS1[g(n)]LCLASS2[h(n)]BLCLASS2[h(f(n))]. Mais c'est simple - l'algorithme décidant que L remplit simplement l'entrée en conséquence et exécute B ' sur l'entrée rembourrée.BLB

Cette étape peut être résumée comme suit: nous voulons décider dans la classe la plus grande et la plus ingénieuse. En utilisant nos ressources supplémentaires, nous complétons l'entrée et exécutons l'algorithme pour décider de la langue remplieL .

Bien sûr, il y a quelques détails techniques impliqués ici (par exemple, nous devons nous assurer que le rembourrage peut être implémenté dans les classes que nous considérons) mais je les ignore simplement pour donner l'intuition générale.

Karolina Sołtys
la source
13

Je vois les arguments de remplissage en termes de compacité de la représentation. Pensez à deux traducteurs Turing: fait exploser les instances et C les comprime à nouveau.BC

L'argument padding fonctionne avec , en composant B avec la version déterministe de la MT pour le langage de la classe non déterministe inférieure. Les sorties de B forment collectivement un langage qui n'est pas représenté de manière compacte, donc cela devient "plus facile".BBB

Il n'est pas possible d'appliquer l'idée dans l'autre sens, en utilisant , car seuls certains des langages de la classe facile sont générés en faisant exploser les langages de la classe dure.C

András Salamon
la source
5

Pour le rendre plus intuitif, regardons ce qui se passe de manière plus abstraite!

Nous avons deux transformations, une pour les entrées et une pour les problèmes. Je les désignerai toutes les deux par , il sera clair d'après le contexte quand il s'agit de la première et quand il s'agit de la seconde.pad

Ces deux transformations ont la propriété suivante:

I. pour tous les problèmes , pour toutes les entrées x Σ :AΣxΣ

ssi x A ,pad(x)pad(A)xA

II. si est dans E X P ( N E X P ), alors p a d ( A ) est dans P ( N P ).AEXPNEXPpad(A)PNP

III. la transformation des entrées est dans la classe de complexité ,EXP

Il est clair que les transformations de remplissage ont ces propriétés.

Maintenant, la raison pour laquelle nous ne savons pas faire la même chose dans le sens inverse est que nous n'avons pas de transformations comme le remplissage dans le sens inverse (lorsque nous échangeons avec P et N E X P avec N P ). Donc la question est pourquoi?EXPPNEXPNP

Je n'ai pas d'argument formel pourquoi il n'y a pas de telles transformations pour le moment, mais intuitivement ce qu'András Salamon a dit est correct. Il est facile d'augmenter la taille des entrées, mais on ne sait pas comment les compresser?

Une autre façon de le comprendre est de penser de la manière suivante. Supposons que , et nous voulons résoudre un problème N E X P = N T i m e ( 2 n O ( 1 ) ) . On nous donne une entrée x de longueur n , nous la considérons comme une entrée de longueur N = 2 n O ( 1 ) :P=NPNEXP=NTime(2nO(1))xnN=2nO(1)

NEXP(n)=NTime(2nO(1))=NTime(N)NP(N)P(N)=Time(NO(1))=Time(2nO(1))=EXP(n)

Kaveh
la source
1
N=log(n)
1
Une troisième façon d'y penser, en fait, est de regarder l'inverse. Je n'ai pas suivi cette approche jusqu'à la fin, mais si une grande perspicacité vient, je la posterai en réponse à moi-même.
gabgoh
1
@gabgoh: C'est plus délicat que le simple changement de variables. Je pense que l'entrée est de longueurN=2nO(1), cela fonctionne parce que nN, J'imagine juste qu'il y a suffisamment de blancs à la fin de l'entrée d'origine pour rendre la longueur égale à N, mais comment penser à une entrée de longueur n comme étant de longueur N=bûche(n)? Don't forget that what is inside the parenthesis is the length of the input! i.e. that is the part of the input that the output of the function is going to depend on.
Kaveh
1
[continued] Considering this might also help: assume that the input is in unary and of length n, then we can compress it to N=log(n) bits and actually that would work! A problem which is P (NP) with unary encoding will be in EXP (NEXP) with binary encoding.
Kaveh
1
I guess my trouble is with the phrase "thinking of", I can't wrap my head around what it means to think of a smaller input as a larger input, and what that does, in reality. I do realize that you can't think of N=log(n), for the reason you state, which is a restatement of the padding argument, not a clean analogy I suppose. After all, when we change variables we are always thinking of variables in terms of other variables, but unlike real variables it's kinda "incompressible". Not to say it is a bad answer, but it doesn't help me much personally.
gabgoh