Inwieweit hilft die Rechenfähigkeit für schwierige Aufgaben bei der Lösung einfacher Aufgaben

Kurz gesagt, die Frage ist: Inwieweit hilft Ihnen die Rechenfähigkeit für schwierige Aufgaben wirklich bei der Lösung einfacher Aufgaben. (Es gibt verschiedene Möglichkeiten, diese Frage interessant und nicht trivial zu machen, und hier ist ein solcher Versuch.)

Frage 1:

Betrachten Sie eine Schaltung zum Lösen von SAT für eine Formel mit n Variablen. (Oder um den Hamilton-Zyklus für einen Graphen mit Kanten zu finden.)$n$

Angenommen, jedes Gate erlaubt die Berechnung einer beliebigen Booleschen Funktion für Variablen. Der Vollständigkeit halber nehmen wir m = 0,6 n .$m$$m=0.6 n$

Die Hypothese der starken exponentiellen Zeit (SETH) besagt, dass wir selbst bei solch starken Gattern eine Superpolynomschaltungsgröße benötigen. Tatsächlich benötigen wir für jedes ϵ eine Größe von mindestens . In gewisser Weise bieten Gates für einen Bruchteil der Variablen, die sehr komplizierte Boolesche Funktionen darstellen (weit über die NP-Vollständigkeit hinaus), keinen großen Vorteil.$\Omega (2^{(0.4-\epsilon) n})$$\epsilon.$

Wir können weiter fragen:

(i) Können wir eine solche Schaltung der Größe ? 2 ( 1 - ϵ ) n ?$2^{0.9 n}$$2^{(1-\epsilon)n}$

Eine "Nein" -Antwort wird eine enorme Stärkung des SETH sein. Natürlich gibt es vielleicht eine einfache Ja-Antwort, die ich einfach vermisse.

(ii) Wenn die Antwort auf (i) JA lautet, bieten Gates, die beliebige Boolesche Funktionen berechnen, einige Vorteile gegenüber Gates, die „nur“ beliebige NP-Funktionen berechnen (sagen wir); oder nur kleinere Instanzen von SAT selbst?

Die nächste Frage versucht, etwas Ähnliches für Fragen in .$P$

Frage 2:

Wie zuvor sei und der Vollständigkeit halber sei m = 0,6 n . (Andere Werte von m , wie beispielsweise m = n α sind ebenfalls von Interesse.) Die folgenden Arten von Schaltungen:$m< n$$m=0.6n$$m$$m=n^\alpha$

a) In einem Schritt können Sie eine beliebige Boolesche Funktion für Variablen berechnen.$m$

b) In einem Schritt können Sie ein SAT-Problem mit Variablen lösen . Oder vielleicht eine beliebige nichtdeterministische Schaltung mit Polynomgröße in m Variablen.$m$$m$

c) In einem Schritt können Sie eine beliebige Schaltung für Variablen der Größe m d durchführen ( d ist fest).$m$$m^d$$d$

d) In einem Schritt können Sie gewöhnliche Boolesche Gatter ausführen.

$n$

(Dies kann mit bekannten Problemen bei der parallelen Berechnung oder bei Orakeln zusammenhängen.)

$2^{2^m \cdot s}$$s$$s=2^{n-m}$