Umfang der natürlichen Beweisbarriere

Die natürliche Beweisbarriere von Razborov und Rudich besagt, dass man unter glaubwürdigen kryptographischen Annahmen nicht hoffen kann, NP von P / poly zu trennen, indem man kombinatorische Eigenschaften von Funktionen findet, die konstruktiv, groß und nützlich sind. Es gibt mehrere bekannte Ergebnisse, die es schaffen, die Barriere zu umgehen. Es gibt auch mehrere Veröffentlichungen, in denen mögliche Lücken für die drei Bedingungen besprochen werden, z. B. das Ergebnis von Chow, dass die Barriere empfindlich gegen schwache Verstöße gegen die Größe ist, und eine kürzlich erschienene Veröffentlichung von Chapman und WilliamsVorschläge, wie die Barriere möglicherweise durch Lockerung der Nützlichkeitsbedingung vermieden werden kann. Meine Frage ist, ob es Beispiele oder sogar die Möglichkeit gibt, die natürliche Beweisbarriere nicht dadurch zu umgehen, dass man die Konstruktivität, die Größe oder den Nutzen verletzt, sondern dass man völlig außerhalb seines Geltungsbereichs fällt. Das heißt, es ist mir überhaupt nicht klar, warum jede mögliche Beweismethode darauf beruhen sollte, kombinatorische "Eigenschaften" zu finden und dann alle Funktionen in diejenigen zu unterteilen, die die Eigenschaft erfüllen und nicht erfüllen. Warum muss dieser Rahmen für alle möglichen Beweise gelten, und wenn dies nicht der Fall ist, wie würden andere Arten von Beweisen aussehen?

Sei eine Funktion und sei C eine Klasse von Algorithmen, die mit endlichen Schichten von f arbeiten . Jede Schaltung gebunden niedriger ist auch immer ein Beweis dafür , dass f ∉ C , für einige f und einige C . Betrachten Sie die "kombinatorische Eigenschaft von Booleschen Funktionen" P f , so dass$f: \{0,1\}^* \rightarrow \{0,1\}$$C$$f$$f \notin C$$f$$C$${\cal P}_f$

und P f (g)=0für alleg≠f.${\cal P}_f(f) = 1$${\cal P}_f(g) = 0$$g \neq f$

Ein Beweis, dass ein Beweis ist, dass P f in der Terminologie von Razborov und Rudich gegen C nützlich ist . Das heißt, "Nützlichkeit" ist absolut unvermeidlich - es gibt keine Möglichkeit, "außerhalb seines Geltungsbereichs zu fallen". Wenn Sie eine Schaltkreisuntergrenze bewiesen haben, haben Sie eine nützliche Eigenschaft angegeben.$f \notin C$${\cal P}_f$$C$

Man beachte , dass, wenn , dann P f sowie auch konstruktiv ist, in der Terminologie der Razborov und Rudich. Also für Funktionen f berechenbar innerhalb E aber nicht in (sagen wir) P / p o l y würde Konstruktivität auch mindestens eine Eigenschaft von Booleschen Funktionen anwenden , die gegen nützlich ist , P / p o l y .$f \in TIME[2^{O(n)}]$${\cal P}_f$$f$$E$$P/poly$$P/poly$

Razborov und Rudich sind also fundamentaler, als Sie vielleicht zunächst denken.

Sie haben Recht: Der Satz über natürliche Beweise handelt von natürlichen Eigenschaften (und nur informell von Beweisen). Razborov selbst hat ungefähr zur gleichen Zeit zwei Artikel geschrieben, in denen er sich mit der Klasse der formalen Beweise und den unteren Grenzen der Komplexität befasste:

• Bounded Arithmetic und Lower Bounds in Boolean Complexity , 1995
• Unbeweisbarkeit niedrigerer Schranken für die Schaltkreisgröße in bestimmten Fragmenten der begrenzten Arithmetik , 1995

Die erste Studie untersucht die Formalisierung bestehender Beweise für untere Schranken in schwachen Fragmenten der Arithmetik (obere Schranken für die Härte des Beweises der unteren Schranken der Komplexitätstheorie).

In der zweiten Arbeit geht es um Untergrenzen für die Härte des Nachweises einer stärkeren Komplexitätstheorie. Untergrenzen: Wie viel Mathematik brauchen wir, um zu beweisen ? $\mathsf{P} \neq \mathsf{NP}$Brauchen wir ? Z F ? P A ? Vielleicht mindestens P V ? ( P V wird als die Theorie betrachtet, die der Argumentation unter Verwendung der Konzepte in P entspricht ). Ein ideales Ergebnis für das zweite Papier wäre gewesen:$ZFC$$ZF$$PA$$PV$$PV$$\mathsf{P}$

kann nicht beweisen(eine vernünftige Formalisierung) P ≠ N P .$PV$$\mathsf{P} \neq \mathsf{NP}$

$PV$

$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P}$