Gibt es ein Analogon der Komplexitätstheorie zu Rices Theorem in der Berechenbarkeitstheorie?

Der Satz von Rice besagt, dass jede nichttriviale Eigenschaft der Menge, die von einer Turing-Maschine erkannt wird, unentscheidbar ist.

Ich suche nach einem komplexitätstheoretischen Satz vom Typ Reis, der uns sagt, welche nichttrivialen Eigenschaften von NP-Mengen nicht zu handhaben sind.

Eine solch komplexitätstheoretische Version von Rices Theorem zu beweisen, war für mich eine Motivation, die Programmverschleierung zu studieren.

Der Satz von Rice besagt im Wesentlichen, dass es angesichts des Programms schwierig ist, die Funktionen zu verstehen, die Programme berechnen. Der Grund, warum diese Probleme unentscheidbar sind, ist, dass sie unendlich sind. Selbst bei einer Eingabe kann ein Programm niemals anhalten, und wir müssen überlegen, was das Programm bei unendlich vielen Eingaben tut.

Eine finitäre Version von Rices Theorem würde die Eingabegröße und die Laufzeit eines Programms festlegen und sagen, dass das Programm schwer zu verstehen ist. Sobald Sie diese behoben haben, können Sie das Programm auch als Boolesche Schaltung anzeigen. Welche Eigenschaften der von einer Booleschen Schaltung berechneten Funktion sind schwer zu berechnen? Ein Beispiel ist "nicht immer 0", was die NP-vollständigen Erfüllbarkeitsprobleme sind. Aber im Gegensatz zu Rices Theorem gibt es einige Eigenschaften, die nicht trivial, aber einfach sind, auch ohne die Schaltung zu verstehen. Wir können immer wissen, dass die von einer Schaltung berechnete Funktion eine begrenzte Schaltungskomplexität hat (die Größe der Schaltung). Wir können die Schaltung auch immer an Eingängen unserer Wahl auswerten.

Nehmen wir also an, eine Eigenschaft von ist beim Black-Box-Zugriff einfach, wenn sie in probabilistischer Polynomzeit durch einen Algorithmus berechnet werden kann, der als Eingabe n eine Schranke an | erhält C | und Oracle Zugriff auf f C . Zum Beispiel ist die Erfüllbarkeit beim Black-Box-Zugriff nicht einfach, da wir uns eine Schaltung der Größe n vorstellen könnten , die nur die Antwort 1 für eine zufällig ausgewählte Eingabe x erzeugt . Kein Black-Box-Algorithmus konnte eine solche Schaltung von einer unterscheiden, die immer 0 zurückgab, da die Wahrscheinlichkeit, das Orakel auf x abzufragen, exponentiell gering ist. Andererseits ist die Eigenschaft f ( 0..0 $f_C$$n$$|C|$$f_C$$n$$x$$x$ ist Blackbox einfach. Die Frage ist:Gibtes Eigenschaften von f C , die in der Wahrscheinlichkeitspolynomzeit entscheidbar sind und die mit dem Black-Box-Zugriff nicht einfach sind?$f(0..0)=1$$f_C$

Obwohl diese Frage meines Wissens offen ist, wurde unser beabsichtigter Ansatz ausgeschlossen. Wir hatten gehofft, dies zu beweisen, indem wir zeigten, dass eine kryptografisch sichere Programmverschleierung möglich war. Boas bewies jedoch das Gegenteil: dass es unmöglich war. Dies zeigt implizit, dass der Black-Box-Zugriff auf Schaltkreise eingeschränkter ist als der vollständige Zugriff auf die Schaltkreisbeschreibung, aber der Beweis ist nicht konstruktiv, so dass ich keine Eigenschaft wie oben nennen kann, die angesichts der Schaltkreisbeschreibung einfach ist, aber nicht mit Schwarz -Box-Zugang. Es ist (zumindest für mich) interessant, ob eine solche Eigenschaft aus unserem Papier rückentwickelt werden kann.

Hier ist die Referenz: Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: Über die (Im) Möglichkeit der Verschleierung von Programmen. CRYPTO 2001: 1-18

Im Laufe der Jahre wurden mehrere solcher Theoreme bewiesen. In jüngerer Zeit wurden Anstrengungen unternommen, um "Reis-artige" Theoreme für Probleme auf Schaltkreisen aufzustellen. (Es ist natürlich, "Maschinen" durch "Schaltkreise" zu ersetzen. Sobald Sie dies tun, wird die Gesamtzahl der möglichen Eingaben festgelegt, sodass Sie nicht auf Unentscheidbarkeitsprobleme stoßen.) Zwei Referenzen:

Bernd Borchert, Frank Stephan: Auf der Suche nach einem Analogon zum Reissatz in der Schaltungskomplexitätstheorie. Mathematik. Log. Q. 46 (4): 489-504 (2000)

Lane A. Hemaspaandra, Jörg Rothe: Ein zweiter Schritt in Richtung komplexitätstheoretischer Analoga von Rices Theorem. Theor. Comput. Sci. 244 (1-2): 205-217 (2000)

Hier ist ein Beispielergebnis: "Jede nicht leere ordnungsgemäße Zähleigenschaft von Schaltkreisen ist UP-hart." Sie können die Papiere für Definitionen lesen, aber dies bedeutet grob, dass jede Eigenschaft, die von der Anzahl der erfüllenden Zuordnungen zu einem Stromkreis abhängt, für die Klasse UP schwierig ist (daher schwer zu handhaben).

Es gibt auch ältere Arbeiten zu komplexitätstheoretischen Versionen von Rices Theorem in einem anderen Sinne. Ich kenne mich damit nicht aus, aber die obigen Papiere zitieren sie.

$NP$$NP$$NP$