Avons-nous des circuits uniformes non triviaux?

Étant donné un algorithme fonctionnant au temps , nous pouvons le convertir en une famille de circuits uniformes "triviaux" pour le même problème de taille au plus ≈ t ( n ) log t ( n ) .$t(n)$$\approx t(n)\log t(n)$

D'un autre côté, il se pourrait que nous ayons des circuits uniformes beaucoup plus petits pour ce problème, même si est un temps de fonctionnement optimal. Les circuits peuvent prendre plus de temps que t ( n ) à générer, mais ils sont petits.$t(n)$$t(n)$

Mais savons-nous réellement comment construire de telles choses? Je pense que la question initiale à poser est

(1) Avons-nous des exemples constructifs de circuits uniformes non triviaux, c'est -à- dire des circuits uniformes dont la taille est inférieure au temps de fonctionnement le plus connu de tout algorithme pour le même problème?

Maintenant, je crois que si un problème est dans , alors nous avons un algorithme à temps exponentiel pour trouver des circuits optimaux en utilisant une recherche exhaustive: Étant donné n , nous notons les réponses sur les 2 n entrées (prenant le temps ( 2 n ) t ( n ) ); puis nous énumérons tous les circuits sur n entrées de taille croissante jusqu'à ce que l'on trouve un qui donne toutes les bonnes réponses. La recherche se termine à la taille de la conversion triviale, t ( n ) $\mathsf{DTIME(t(n))}$$n$$2^n$$(2^n)t(n)$$n$ , ou la table de vérité de la fonction, 2 n si les sorties sont { 0 , 1 } . (Edit: Thomas souligne que la limite est O ( 2 n / n ) en raison de Shannon / Lupanov.)$t(n) \log t(n)$$2^n$$\{0,1\}$$O(2^n/n)$

Nous avons donc un «oui» insatisfaisant à la question (1): prenons une langue qui est difficile à tout moment au-dessus de , mais qui reste décidable; la procédure ci-dessus génère une table de vérité de taille 2 n .$2^n$$2^n$

Nous devons donc affiner la question (1). Je pense que les deux cas les plus intéressants sont

(2) Avons-nous des exemples constructifs de circuits uniformes non triviaux de taille polynomiale ? (Même s'ils sont générés par des algorithmes très lents.)

(3) Avons-nous des exemples constructifs de circuits uniformes non triviaux générables en temps polynomial et de taille polynomiale?

C'est peut-être trop demander. Que diriez-vous d'une question plus simple: savons-nous même qu'une telle chose est possible? Peut-être n'existe-t-il pas de circuits uniformes non triviaux?

(4) La déclaration suivante est-elle connue comme fausse pour tout ? (Edit: o ( 2 n / n ) , merci Thomas.) "Si un langage L a des circuits uniformes de taille O ( s ( n ) ) , alors il a aussi des algorithmes fonctionnant dans le temps ˜ O ( s ( n ) $s(n) = o(2^n)$$o(2^n/n)$$L$$O(s(n))$$\tilde{O}(s(n))$ . " (Dans l'affirmative, qu'en est-il lorsque "uniforme" est remplacé par "uniforme polynomial-temporel", "uniforme de l'espace de journalisation", etc.?)

Enfin, si les questions ci-dessus sont trop difficiles,

(5) Avons-nous des constructions de familles uniformes de circuits qui ne sont pas simplement des conversions d'algorithmes en circuits (ou écrire la table de vérité)?

Postscript. Un expert que j'ai interrogé à ce sujet a mentionné "On Medium-Uniformity and Circuit Lower Bounds" ( pdf ), Santhanam et Williams 2013, qui est peut-être le travail le plus étroitement lié, mais il prouve les limites inférieures (que les circuits pouvant être générés par le temps poly ne sont pas trop puissant). Je serais intéressé par tout autre travail connexe!

Voici les réponses à vos deux dernières questions.

(5) Les réseaux de tri sont des circuits uniformes qui trient aussi rapidement que les meilleurs algorithmes RAM, mais ne sont certainement pas uniquement des conversions d'algorithmes RAM (par exemple, quicksort). [ AKS83 , G14 ]

$s(n)=(1+\varepsilon) \cdot 2^n/n$ avec $\varepsilon>0$, mais pour une raison stupide: chaque fonction est calculée par un circuit de taille $(1+o(1)) \cdot 2^n/n$. ( Shannon l'a prouvé jusqu'à une constante et Lupanov a obtenu la constante optimale.) D'après le théorème de la hiérarchie temporelle, il existe une fonction$f$ avec une complexité temporelle uniforme entre $\Omega(3^n)$ et $O(n \cdot 3^n)$. Cela donne un contre-exemple:$f$ a des circuits de taille $O(2^n/n)$(qui je pense sont calculables dans$2^{\mathrm{poly}(n)}$ temps) mais n'est pas calculable en $\tilde{O}(2^n/n)$temps. Vous devriez probablement demander$s(n) = o(2^n/n)$.

C'est une question intéressante; J'espère que quelqu'un pourra répondre (1) - (3).