Caractérisation de la complexité du circuit pour DLogTime et NLogTime

$\mathsf{DLogTime}$ et$\mathsf{NLogTime}$ sont deux des classes de complexité les plus petites que nous ayons. (Notez que la hiérarchie temporelle logarithmique$\mathsf{LH}$ est égale à$\mathsf{AC}^0$ et ce sont les deux premiers niveaux de$\mathsf{LH}$ ).

Après avoir lu cette question , je deviens curieux de voir si la séparation entre ces deux classes est connu, et en fait , il est facile de les séparer depuis (merci à Robin Kothari. Voir aussi connu$OR(x_1,...,x_n) \in \mathsf{NLogTime}-\mathsf{DLogTime}$). Maintenant, je suis intéressé de connaître leur caractérisation de complexité de circuit correspondante. J'ai cherché un peu et j'ai demandé à quelques personnes mais je n'ai pas pu trouver la réponse.

Avons-nous de belles caractérisations de la complexité des circuits pour les classes de complexité et N L o g T i m e ?$\mathsf{DLogTime}$$\mathsf{NLogTime}$

Remarque: apparaît beaucoup dans la définition de l'uniformité pour les petites classes de complexité. Notez que la petite limite de temps ne permet pas à ces machines de lire l'intégralité de l'entrée, elles ne peuvent lire que lg n bits à partir de l'entrée, et les classes sont définies à l'aide de machines qui peuvent écrire l'adresse d'un bit, puis lire ce bit directement ( c'est-à-dire que vous n'avez pas besoin de parcourir tous les bits précédents pour y arriver).$\mathsf{DLogTime}$$\lg n$

Je pense qu'il est beaucoup plus intéressant que les classes de complexité de circuit utilisées par la théorie de la complexité CS fassent des prédictions différentes et utilisent des métriques différentes de celles de la communauté VLSI. De la complexité VLSI des fonctions booléennes :

Il est bien connu que toutes les fonctions booléennes de variables peuvent être calculées par un circuit logique àportes O ( 2 n / n ) (théorème de Lupanov) et qu'il existe des fonctions booléennes de n variables qui nécessitent des circuits logiques de cette taille (Shannon's théorème). Nous présentons les résultats correspondants pour les fonctions booléennes calculées par les circuits VLSI, en utilisant le modèle de Thompson d'une puce VLSI. Nous prouvons que toutes les fonctions booléennes de n variables peuvent être calculées par un circuit VLSI de zone O ( 2 n ) et de période 1, et nous prouvons qu'il existe des fonctions booléennes de$n$$O(2^n/n)$$n$$O(2^n)$$n$variables pour lesquelles chaque puce VLSI (convexe) doit avoir une zone .$\Omega(2^n)$

Fait intéressant, la complexité des circuits VLSI a tendance à traiter la profondeur comme "non pertinente" car il y a une et une seule "profondeur" qui importe: le chemin critique. Pour la plupart des applications pratiques, un circuit arbitrairement complexe peut être traité comme avec une latence de n .$O(1)$$n$

En fait, je ne suis même pas sûr que le concept de / N L o $DLogTime$ se traduise directement par la complexité du circuit VLSI. Même le résultat Shannons 2 n / n ne se traduit pas facilement: les résultats Shannons ne sont valablesquepour une base booléenne composée d'une arité ≤ 2 {AND, OR, NOT}. Ce n'est pas la seule base, et le nombre de «portes» nécessaires diminue considérablement à mesure que vous autorisez de plus en plus de types de portes. Les éléments suivants sont a r e a $NLogTime$$2^n/n$$\le2$$area^2$ à partir d'une bibliothèque de cellules standard VLSI commerciale normalisée à la taille d'une porte NAND à 2 entrées:

        2 3 4 <- Arity
et 1,14 1,28 1,41
non 1,00 1,14 1,28
ou 1,14 1,41 1,41
ni 1,00 1,14 1,41
xor 1,62 2,44
xnor 1,62 2,44

buf 1.14
inv 0.80

aoi22 1,28
aoi222 1,62
aoi33 1.62
oai22 1,41
oai222 1,72
oai33 1,62

addf 2.64

Plus précisément, notez les portes aoi/ oaiqui sont And Or Invert/ Or And Invertconsistant en une première fonction de taille d' arité alimentant la deuxième fonction, où le nombre de portes de première fonction est égal au nombre de fois où l' arité apparaît. Par exemple, représente "Deux portes ET à 2 entrées alimentant une porte NOR".aoi22

Mon point est: Pris séparément, une oai222fonction peut être construite en utilisant trois portes OU à 2 entrées et une porte NAND à 3 entrées, pour une superficie totale de ~ 4,56, sans compter toute zone utilisée pour l'interconnexion. Pourtant, cette primitive peut être réalisée dans une zone de seulement 1,72, ce qui signifie qu'une manifestation discrète de la même fonction booléenne consomme 2,65 fois plus de surface.

Notez également que la zone pour un $n$ entrée {AND, NAND, OR, NOR, XOR, XNOR}, où , est beaucoup moins que la zone qu'il faudrait pour construire la même fonction en utilisant des portes d'entrée à 2 entrées discrètes. Notez également que bien que la zone donnée pour {XOR, XNOR} pour ce processus soit "grande" par rapport aux autres portes, il existe d'autres façons de construire les mêmes n portes d'entrée en utilisant moins de surface.$n\ge2$$n$

Les propriétés de propagation pour les primitives plus complexes sont également nettement meilleures que celles qui seraient obtenues en utilisant des portes discrètes.

Pourquoi est-ce important? Parce que pour moi, au moins, j'ai passé énormément de temps à parcourir les résultats de la théorie de la complexité qui sont construits sur un ensemble d'hypothèses qui ont pour effet de rendre le résultat inutile ou faux une fois l'hypothèse violée. Ce qui suit est de Steven Cooks vs N $\mathcal{P}$$\mathcal{NP}$ :

Ainsi , pour prouver il suffit de prouver un super-polynomiale minorant la taille d'une famille de circuits booléens résoudre certains spécifiques N P problème -complete, comme le 3-SAT. En 1949, Shannon a prouvé que pour presque toutes les fonctions booléennes f : { 0 , 1 } n → { 0 , 1 } , tout circuit booléen calculant f nécessite au moins $\mathcal{P} \ne \mathcal{NP}$$\mathcal{NP}$$f : \{0,1\}^n \to \{0,1\}$$f$portes n / n . Malheureusement, son argument de comptage ne donne aucune idée de la façon de prouver les limites inférieures des problèmes dans N $2^n/n$$\mathcal{NP}$.

Je trouve les cuisiniers curieux. Le résultat de Shannons est valable pour tous les , donc si un problème N P peut être décrit dans { 0 , 1 } n bits, il doit y avoir un {AND, OR, NOT} circuit de base qui peut décider s'il est satisfaisable en ~ 2 n $f : \{0,1\}^n \to \{0,1\}$$\mathcal{NP}$$\{0,1\}^n$ portes (le papier réel donne une limite supérieure, mais finie, plus grande pour chaque fonction possible). Ce que cela nous dit, c'est que tout ce qui utilise plus de n portes, où$2^n/n$$n$$n$est la limite supérieure de la taille du problème , utilise plus de portes que nécessaire. L'utilisation d'une base booléenne plus grande mais complète ne réduit que le nombre de portes nécessaires. L'utilisation d'un modèle de complexité de circuit différent, c'est-à-dire VLSI, donne des limites de résultats encore «meilleures». Curieuse. Mais nous savons pertinemment que toute solution à un problème N P qui utilise plus de ~ 2 n / n "portes" (où les portes sont utilisées de manière lâche pour les étapes / opérations) le fait de manière sous-optimale ... et il existe un nombre infini de façons de trouver une solution de manière sous-optimale.$\mathcal{NP}$$\mathcal{NP}$$2^n/n$

Sur la complexité des implémentations VLSI et des représentations graphiques des fonctions booléennes avec application à la multiplication entière montre que la prédiction de la complexité du circuit à l'aide d'un modèle OBDD surestime la complexité réelle du circuit:

$AT^2 = \Omega (n^2)$$\Omega(c^n)$$c<1$$AT^2 = O(n^{1+c})$

$n$$2n-1$$i-1$$2n-i-1$$1\le i\le n$$AT^2 = \Omega(i^2)$$\Omega(1.09^i)$