Quels sont les exemples de la façon dont la non-uniformité peut être utile?

9

Je suis curieux de savoir comment vous avez vu la non-uniformité être utile dans le calcul. Une façon est le caractère aléatoire, comme dans , et une autre est des tables de recherche qui sont utilisées pour montrer que toutes les langues ont des circuits non uniformes.BPPP/poly

En particulier, je m'intéresse aux façons dont les objets connus pour exister via la méthode probabiliste et d'autres méthodes de preuve non constructives (ou pas suffisamment constructives) peuvent être exploités en utilisant la non-uniformité. Je préfère que les exemples soient naturels et non artificiels. Pour être clair, un circuit pour un problème artificiel pourrait être quelque chose comme: étant donné un langage , je crée un circuit de taille polynomiale en calculant une fonction vraiment difficile utilisant mes conseils et en me demandant si .f ( | x | ) f ( | x | ) n / | f ( | x | ) | x LLPF(|X|)F(|X|)n/|F(|X|)|XL

Samuel Schlesinger
la source
Donc, par «utile», je suppose que vous entendez une diminution significative des ressources nécessaires pour résoudre le problème? par exemple des circuits non uniformes qui sont significativement plus petits que des circuits uniformes, ou des machines de turing avec des conseils qui fonctionnent beaucoup plus rapidement que tout sans conseil?
usul
Ce sont équivalents, non? Je voulais vraiment dire utile comme dans "utilisé pour prouver quelque chose d'intéressant", cependant
Samuel Schlesinger
Je suppose que j'imagine que toutes les choses intéressantes que vous prouveriez en utilisant la non-uniformité tomberaient essentiellement dans ce que vous dites, sauf que peut-être que les circuits seront meilleurs que ceux uniformes connus, mais pas meilleurs que ceux possibles
Samuel Schlesinger

Réponses:

11

Un exemple que j'aime est l'argument selon lequel en comptant les chaînes dans la langue (voir par exemple https://blog.computationalcomplexity.org/2004/01/little-theorem.html ) .NEcoNE/(n+1)

Emil Jeřábek
la source
C'est très bien, car cela ne dépend pas de la méthode probabiliste ou des tables de recherche. Merci pour cela.
Samuel Schlesinger
(Notez que si la longueur de conseils chaîne doit être exacte, alors ne fonctionne pas tout à fait évidemment (et je ne vois aucune façon de montrer que cela fonctionne, évident-nor-pas).)n
Je pense que les cours de conseil ne sont généralement pas définis pour avoir une durée de conseil exacte @RickyDemer
Samuel Schlesinger
De plus, je ne peux pas voir cela dans mes tentatives jusqu'à présent, donc si quelqu'un pouvait donner une référence ou mentionner comment le voir, j'apprécierais
Samuel Schlesinger
1
@SamuelSchlesinger: Alors que P / poly ou C / log (pour toute classe C) sont généralement définis avec une longueur de conseil allant jusqu'à big-Oh, ce n'est pas toujours vrai. Certains résultats utilisent un nombre exact de bits de conseil (parfois aussi petit que 1!).
Joshua Grochow
10

NLUL/polyGnggst

BPPP/polyNL=UL

William Hoza
la source
6

Je ne sais pas si cela correspond à ce que vous recherchez, mais il y a quelques résultats prouvant les théorèmes de hiérarchie pour les classes de complexité sémantique avec un petit conseil, où aucun théorème de hiérarchie n'est connu sans conseil. L'exemple le plus connu est BPP, pour lequel nous ne connaissons pas de théorème de hiérarchie, mais Fortnow et Santhanam ont montré qu'il en existe un avec un conseil (en s'appuyant sur un résultat de Barak qui a utilisé plus de conseils). Cet article de Melkebeek et Pervyshev donne des références et l'histoire, et un théorème qui semble subsumer les précédents.

Sasho Nikolov
la source
P/log
@Turbo Affirmez-vous que BPP / 1 est identique à BPP. Essayez d'écrire une preuve et vous devriez être en mesure de voir facilement par vous-même où cela se passe mal
Sasho Nikolov