Le pouvoir déraisonnable de la non-uniformité

33

Du point de vue du sens commun, il est facile de croire que l’ajout du non-déterminisme à P étend considérablement son pouvoir, c’est-à-dire que NP est beaucoup plus grand que P . Après tout, le non-déterminisme permet un parallélisme exponentiel, qui apparaît sans aucun doute très puissant.

D'un autre côté, si nous ajoutons simplement la non-uniformité à et obtenons P / p o l y , alors l'intuition est moins claire (en supposant que nous excluions les langages non récursifs qui pourraient se produire dans P / p o l y ). On pourrait s'attendre à ce que le fait d'autoriser différents algorithmes de temps polynomial pour différentes longueurs d'entrée (sans quitter le domaine récursif) constitue une extension moins puissante que le parallélisme exponentiel dans le non-déterminisme.PP/polyP/poly

Fait intéressant, cependant, si nous comparons ces classes à la très grande classe , nous voyons alors la situation contre-intuitive suivante. Nous savons que N E X P contient correctement N P , ce qui n’est pas surprenant. (Après tout, N E X P permet une double parallélisme exponentielle.) D'autre part, actuellement nous ne pouvons pas exclure N E X PP / p o l yNEXPNEXP NPNEXPNEXPP/poly .

Ainsi, dans ce sens, la non-uniformité, ajoutée au temps polynomial, le rend éventuellement extrêmement puissant, potentiellement plus puissant que le non-déterminisme. On pourrait même aller jusqu'à simuler un parallélisme doublement exponentiel ! Même si nous pensons que ce n’est pas le cas, mais le fait qu’il ne puisse pas être exclu à l’heure actuelle laisse néanmoins penser que les théoriciens de la complexité luttent contre de «puissantes puissances».

Comment expliqueriez-vous à un profane intelligent ce qui se cache derrière ce "pouvoir déraisonnable" de non-uniformité?

Andras Farago
la source
16
La difficulté à comprendre la non-uniformité (et à prouver les limites inférieures des circuits généraux) n'implique pas nécessairement que la non-uniformité soit puissante (en ce sens que vous pouvez l'utiliser pour résoudre des problèmes intéressants).
Kaveh
4
Je ne pense pas que quiconque croit ou même N PP / p o l y . Le fait que ces questions restent en suspens est davantage une affirmation de notre incapacité embarrassante de prouver les limites inférieures du circuit. NEXPP/polyNPP/poly
Thomas
8
@Thomas: Je ne présumera pas parler pour quelqu'un d' autre, mais dira que je sais au moins un chercheur très respecté qui en effet que des conjectures . EXPP/poly
Joshua Grochow
2
@Thomas: Pas tout à fait, mais je pense que nous comprenons si peu la non-uniformité. Par exemple, pour tout ce que nous savons (et comme l'a supposé Kolmogorov, voir cstheory.stackexchange.com/a/22048/129 ), P a des ckts de taille . Autre exemple, il semble qu'il ya peu ( le cas échéant) des problèmes naturels connus pour être dans P / p o l y qui ne sont ni rares ni dans BPP ( cstheory.stackexchange.com/questions/1662/... ). Et pourtant, compte tenu CKTS, on pourrait penser que P / p o l y est nettement plus puissant que + randomisation table de consultation. O(n)P/polyP/poly
Joshua Grochow
6
Faire écho à @ thomas si nous ne pouvons pas prouver que NEXP ne figure pas dans P / poly signifie qu'il existe un "pouvoir déraisonnable de non-uniformité", puisqu’on ne peut pas prouver que P <> NP signifie qu’il doit exister un "pouvoir déraisonnable de calcul efficace".
Lance Fortnow

Réponses:

33

Une réponse rapide est que ce n'est pas la première chose à propos de la théorie de la complexité que j'essaierais d'expliquer à un profane! Pour apprécier même l’idée de non-uniformité, et la différence entre celle-ci et le non-déterminisme, il est nécessaire d’être plus loin dans les mauvaises herbes avec les définitions des classes de complexité que beaucoup de gens sont disposés à obtenir.

Cela dit, j’ai trouvé utile, lorsqu’on explique P / poly à des étudiants de premier cycle, que la non-uniformité signifie que vous pouvez avoir une séquence infinie d’optimismes de mieux en mieux, en passant à des longueurs d’entrée de plus en plus grandes. En pratique, par exemple, nous savons que l’algorithme naïf de multiplication matricielle fonctionne mieux pour les matrices jusqu’à 100x100, et qu’à un moment donné, la multiplication de Strassen devient meilleure et que les algorithmes plus récents ne s’améliorent que pour les matrices de taille astronomique. ne se poserait jamais dans la pratique. Alors, si vous aviez la capacité magique de cibler le meilleur algorithme quelle que soit la plage de n avec laquelle vous travailliez?

Bien sûr, ce serait une capacité étrange, et toutes choses considérées, probablement pas aussi utile que la capacité de résoudre des problèmes NP-complets en temps polynomial. Mais à proprement parler, ce serait une capacité incomparable : ce n’est pas une capacité que vous obtiendriez automatiquement, même si P = NP. En effet, vous pouvez même construire des exemples artificiels de problèmes non calculables (par exemple, en prenant 0 n en entrée, la n- ième machine de Turing s'arrête-t-elle?) Que cette capacité vous permettrait de résoudre. Donc, c'est le pouvoir de la non-uniformité.

Pour comprendre l' intérêt de considérer cet étrange pouvoir, vous aurez probablement besoin de dire quelque chose à propos de la quête de la limite inférieure du circuit et du fait que, du point de vue de nombre de nos techniques de la limite inférieure, c'est l' uniformité qui semble étrange. condition supplémentaire dont nous n'avons presque jamais besoin.

Scott Aaronson
la source
2
J'aime beaucoup l'argument "séquence infinie de meilleurs algorithmes". En fait, je cherchais de tels arguments, qui sont utiles pour expliquer la situation dans son ensemble aux étudiants de premier cycle. Comment cet argument s’appliquerait-il, toutefois, si est remplacé par B P P ? Pour B P P, la même question initiale pourrait être reformulée, car nous ne pouvons actuellement pas séparer N E X PP/polyBPPBPPNEXP de soit. BPP
Andras Farago
7
BPP est beaucoup plus facile à motiver! C'est juste essayer de modéliser la puissance de la randomisation, qui (contrairement à la non-uniformité) est quelque chose qui est utilisé tout le temps dans la pratique. (Soit dit en passant, j’ai oublié de mentionner: une autre façon de motiver la non-uniformité serait la cryptographie. Vous pouvez indiquer que les adversaires ont le luxe d’optimiser toutes leurs ressources d’attaque pour la longueur de clé choisie, ce qui vous permet Il vaudrait mieux avoir un cryptosystème que vous pensez sécurisé contre des attaquants non uniformes de longueur fixe, et pas seulement contre des attaquants uniformes.)
Scott Aaronson
1
Je suis entièrement d'accord pour dire que est plus facile à motiver. Mais qu'est-ce qui n'est pas clair: qu'est-ce qui donne à B P P une puissance telle qu'on ne peut actuellement exclure qu'elle puisse même simuler le parallélisme doublement exponentiel de N E X P ? Puisque B P P ne diffère de la forme P que par le biais du hasard, et qu’il est supposé pour une bonne raison que le caractère aléatoire est ici impuissant (c.-à-d. P = B P P ), cela me semble une situation étrange. Je cherche une "compréhension philosophique" de la situation, au-delà du fait évident que les outils manquent pour prouverBPPBPPNEXPBPPPP=BPP .NEXPBPP
Andras Farago
2
Mais si ce vraiment est juste le fait que les outils manquent? Nous avons les théorèmes de hiérarchie, ce qui nous permet de prouver que plus d'une même ressource vous donne plus de pouvoir (par exemple, ), et lorsque nous ne pouvons pas réduire à un théorème de hiérarchie, nous sommes généralement bloqués. Ceci est un problème général qui se manifeste partout dans la hiérarchie de la complexité, pas quelque chose de spécifique à B P P . PEXPBPP
Scott Aaronson
28

Voici un argument de "finesse" que j’ai entendu récemment pour défendre l’affirmation selon laquelle les modèles de calcul non uniformes devraient être plus puissants que nous le supposons. D’une part, nous savons du théorème de la hiérarchie temporelle qu’il existe par exemple des fonctions calculables en temps qui ne le sont pas en temps O ( 2 n ) . Par contre, selon le théorème de Lupanov, toute fonction booléenne sur n entrées est calculable par un circuit de taille ( 1 + o ( 1 ) ) 2 n / nO(22n)O(2n)n(1+o(1))2n/n . Donc, si nous prétendons que la non-uniformité ne donne pas beaucoup de puissance, c’est que devrait se comporter comme D T I M E ( f ( n ) O ( 1 ) ) , alors cette affirmation devrait cesser brusquement maintenant lorsque f ( n ) devient 2 O ( n ) . Mais ce comportement - deux mesures de complexité vont de pair jusqu'à ce que l'une d'elles devienne soudainement tout-puissant - semble arbitraire et quelque peu anormal.SIZE(f(n))DTIME(f(n)O(1))f(n)2O(n)

D'autre part, si les circuits sont assez puissants que , puis par Karp-Lipton la hiérarchie polynomiale s'effondre au deuxième niveau, ce qui serait aussi étrange: pourquoi quantificateurs soudainement cesser de donner plus de puissance de calcul ? Je ne sais pas où cela nous laisse.NPP/poly

Sasho Nikolov
la source
1
Très intéressant! Cela montre bien que notre compréhension du modèle de calcul non-uniforme (circuit) est encore très loin d’être complète.
Andras Farago
4
Sans dire si un tel effondrement est probable: s'agit-il d'un arrêt soudain de la puissance de calcul au deuxième niveau, alors que cela suffit exactement pour avoir les deux types de quantificateur?
Niel de Beaudrap
@NieldeBeaudrap Point très intéressant. Bien sûr, tout cela (y compris la spéculation dans ma réponse) est plus théologique que mathématique, mais il est amusant de spéculer.
Sasho Nikolov
3
@Sasho: ce n'est pas de la théologie, ni même de l'opinion: c'est de la proto-math, n'est-ce pas? C'est un récapitulatif des idées éventuellement pertinentes et une analyse d'intuition. Pas grand chose à faire quand vous êtes perdu dans les bois, mais c'est plus productif que, par exemple, raconter des histoires de fantômes. :-)
Niel de Beaudrap,
10

P/polyNPPNP

Ensuite, j'essayerais d'expliquer que P/poly is so powerful because for each different length, the TM is given advice that it can trust completely. Then I would mention that we can devise hard (non-TM-computable actually) languages that have 1 word per input length (i.e. unary), so they are in P/poly ! But maybe a polynomial long advice isn't enough to solve all languages in NP, since there we are allowed a different hint for every different input.

On the other hand, I would remind that person that NP has to verify the answer, not trust it completely. So, we cannot use the same advice for each input length, it may not be verifiable!

Finally, I would mention that complexity theorists believe that there are languages in NP that require more than polynomial many hints for some input length, and thus cannot be in P/poly.

A critical point for giving a good understanding, which I think is also common when teaching the subject for the first time, is making clear that advice and "hint" (i.e. certificate) are different things, and how they differ.

chazisop
la source
10

For me, the starkest illustration of the power of non-uniformity is that a suitably padded version of the Halting Problem is already in P/1. A single bit of advice is then enough to decide this language with a trivial TM that simply returns the advice bit.

Of course, padding an undecidable language by an exponential amount means it is not "morally" in P/poly. But this does show that one needs to be careful when allowing non-uniformity.

András Salamon
la source
3

I have the impression that the real issue here is the unreasonable heavy burden of proof, not the unreasonable power of non-uniformity. As the answers by chazisop and András Salamon already stress, undecidable languages become computable even in very restricted non-uniform languages, because the burden of proof has been completely waived.

The basic intuition why we might get away without a proof is that there are only 2n different inputs of length n, for which we have to check that the circuit gives the correct answer. So it seems like there would be a proof of at most exponential length in n, that the circuit indeed gives the correct answer. But this is only true as long as there exists for each input of length n a proof of at most exponential length in n, that the input is (not) contained in the language (if it is actually (not) contained in the language). Note that exponentially many inputs times an at most exponentially long proof for each input gives a complete proof for all inputs of exponential length, because 2nexp(O(n))=exp(nlog(2)+O(n))=exp(O(n)).

If we require the existence of a proof of at most exponential length in n for non-uniform languages, then we can prove that all these languages are contained in NEXP. The corresponding non-deterministic algorithm just needs a hint that contains both a "small" circuit together with a "small" proof that this circuit really computes what it is supposed to compute.

The same non-deterministic algorithm would also show P/polyNP, if we required instead the existence of proofs of at most polynomial length in n that the circuit is suitable. Notice that this restricted P/poly could still be more powerful than P. Even Karp-Lipton (i.e. that the polynomial hierarchy collapses if NPP/poly) still holds true, but this statement is less interesting than the real Karp-Lipton theorem.

Thomas Klimpel
la source