Hierarchiesatz für die Schaltungsgröße

Ich denke, dass ein Größenhierarchiesatz für die Schaltungskomplexität ein großer Durchbruch in diesem Bereich sein kann.

Ist es ein interessanter Ansatz zur Klassentrennung?

Die Motivation für die Frage ist, dass wir sagen müssen

Es gibt eine Funktion, die nicht mit Schaltkreisen der Größe berechnet werden kann und die mit Schaltkreisen der Größe berechnet werden kann, bei denen . (und möglicherweise etwas in Bezug auf die Tiefe)g ( n ) f ( n ) < o ( g ( n ) $f(n)$$g(n)$$f(n)<o(g(n))$

Wenn also , scheint die Eigenschaft unnatürlich zu sein (sie verletzt die Größe). Wir können natürlich keine Diagonalisierung verwenden, da wir nicht in einer einheitlichen Umgebung sind.$f(m)g(n) \leq n^{O(1)}$

Gibt es ein Ergebnis in diese Richtung?

Tatsächlich kann gezeigt werden, dass es für jedes ausreichend klein ist (weniger als ), Funktionen gibt, die durch Schaltkreise der Größe berechenbar sind, aber nicht durch Schaltkreise der Größe oder sogar , abhängig von der Art der zulässigen Tore.2 n / n f ( n ) f ( n ) - O ( 1 ) f ( n ) - $f$$2^n/n$$f(n)$$f(n)-O(1)$$f(n)-1$

Hier ist ein einfaches Argument, das zeigt, dass es Funktionen gibt, die in der Größe aber nicht in der Größe berechenbar sind .f ( n ) - O ( n $f(n)$$f(n)-O(n)$

Wir wissen das:

1. es gibt eine Funktion , die eine Schaltungskomplexität von mindestens und insbesondere eine Schaltungskomplexität von mehr als erfordert .2 n / O ( n ) f ( n $g$$2^n/O(n)$$f(n)$
2. die Funktion so dass für jeden Eingang ist, ist durch eine Schaltung konstanter Größe berechenbar.z ( x ) = 0 $z$$z(x)=0$$x$
3. Unterscheiden sich zwei Funktionen und nur in einem Eingang, so unterscheidet sich deren Schaltungskomplexität um höchstensg 2 O ( n $g_1$$g_2$$O(n)$

Angenommen, ist an Eingängen ungleich Null . Nennen Sie solche Eingänge . Wir können für jedes die Funktion die die Indikatorfunktion der Menge ; also und .$g$$N$$x_1,\ldots,x_N$$i$$g_i(x)$$\{ x_1,\ldots,x_i \}$$g_0=0$$g_N=g$

Es ist klar, dass einige so sind, dass eine Schaltungskomplexität von mehr als und eine Schaltungskomplexität von weniger als . Aber dann hat eine Schaltungskomplexität von weniger als aber mehr als .$i$$g_{i+1}$$f(n)$$g_i$$f(n)$$g_{i}$$f(n)$$f(n) - O(n)$

Dieses Ergebnis kann mit einem einfachen Zählargument bewiesen werden. Betrachten Sie eine Zufallsfunktion, die auf die ersten Bits der Eingabe angewendet wird . Diese Funktion hat mit ziemlicher Sicherheit eine Schaltungskomplexität ( 1 + o ( 1 ) ) ( 2 k / k ) nach Riordans und Shannons Zählargument und übereinstimmende Obergrenzen. Wenn wir also k so wählen , dass 2 g ( n ) < 2 k / k < f ( n ) / 2 , können wir die Größe $k$$(1+o(1))(2^k/k)$$k$$2g(n) < 2^k/k < f(n)/2$ ab Größe f ( n ) . Beachten Sie, dass die fraglichen Funktionen nicht notwendigerweise berechenbar sind, aber wir können sie mit Standardtechniken in die exponentielle Zeithierarchie setzen (solange wir den richtigen Wert von k berechnen können). Wir können natürlich nicht beweisen, dass eine Grenze größer als 2 n / n ist , da dies die ungünstigste Schaltungskomplexität einer Funktion ist. $g(n)$$f(n)$$k$$2^n/n$

Natürliche Beweise gelten für diese Art von Argument nicht, da die fragliche Eigenschaft "keine kleine Schaltung" aufweist, die (vermutlich) nicht einfach aus der Wahrheitstabelle der Funktion berechnet werden kann. Es ist nicht klar, wie niedrig diese Art der Zählung in Komplexitätsklassen sein kann. Gibt es einen Grund , warum wir nicht ein Zählargument verwenden kann die untere Grenze für beweisen ? Nicht, dass ich davon Wüste. $NE$