sora aoi9a: Komplexität beweisen

In der theoretischen Informatik und speziell in der Theorie der rechnerischen Komplexität beweist Komplexität die Aufgabe, die Rechenressourcen zu verstehen und zu analysieren, die erforderlich sind, um Aussagen zu beweisen oder zu widerlegen. Die Erforschung der Beweiskomplexität befasst sich vorwiegend mit dem Nachweis von unteren und oberen Schranken der Beweislänge in verschiedenen aussagenbezogenen Prüfsystemen. Zu den Hauptherausforderungen der Beweiskomplexität zählt beispielsweise, dass der übliche Aussagenkalkül keine Beweise für polynomiale Größen aller Tautologien zulässt (die tatsächliche Formalisierung eines Aussagenkalküls ist hier unerheblich, da alle natürlichen Formalisierungen nachgewiesen wurden) Polynomial identisch); hier ist die Größe des Beweises einfach die Anzahl der Symbole darin, und es wird gesagt, dass ein Beweis von Polynomgröße ist, wenn er ein Polynom in der Größe der Tautologie ist, die er beweist.

Die systematische Untersuchung der Beweiskomplexität begann mit der Arbeit von Cook und Reckhow (1979), die die grundlegende Definition eines aussagenlogischen Beweissystems aus der Perspektive der rechnerischen Komplexität lieferten. Insbesondere beobachteten Cook und Reckhow, dass der Nachweis der unteren Schranken der Beweisgröße in stärkeren und stärkeren propositionalen Beweissystemen als ein Schritt in Richtung einer Trennung von NP von CoNP (und somit von P von NP) angesehen werden kann, da es ein Beweisfeststellungssystem gibt, das Beweise für polynomiale Größe zulässt für alle Tautologien bedeutet NP = coNP.

Die zeitgenössische Beweiskomplexitätsforschung zieht Ideen und Methoden aus vielen Bereichen der rechnerischen Komplexität, Algorithmen und Mathematik an. Da viele wichtige Algorithmen und algorithmische Techniken als Beweissuchungsalgorithmen für bestimmte Prüfsysteme ausgeführt werden können, impliziert der Nachweis der unteren Schranken dieser Prüflänge die Laufzeituntergrenzen der entsprechenden Algorithmen.

Die mathematische Logik kann auch als Rahmen für die Untersuchung der Propositionsgrößen dienen. Speziell schwache Fragmente der Peano-Arithmetik, die unter dem Namen "Bounded Arithmetic Theories" (Bounded Arithmetic Theories) zusammengefasst werden, dienen als einheitliche Version von aussagenlogischen Beweisen, die verschiedenen aussagenlogischen Beweisen entsprechen.

Polynomialität von Beweisen [ edit ]

Verschiedene aussagenlogische Beweissysteme für die Aussagenlogik, wie der sequentielle Kalkül, die Schnittebenenmethode, die Auflösung usw., können unterschiedliche Beweise liefern für die gleiche Formel. Die Komplexität des Beweises misst die Effizienz des Prüfsystems in der Regel im Hinblick auf die im System für eine gegebene Tautologie (oder eine zweifach und nicht befriedigende Formel) mögliche Mindestgröße von Nachweisen.

Zwei Punkte machen die Untersuchung der Beweiskomplexität nicht trivial:

Die Größe eines Beweises hängt von der Formel ab, die als inkonsistent zu beweisen ist.
Beweismethoden sind im Allgemeinen Familien von Algorithmen, da einige ihrer Schritte nicht eindeutig festgelegt sind. Zum Beispiel basiert die Lösung auf der iterativen Auswahl eines Paares von Klauseln, die gegenüberliegende Literale enthalten, und es wird eine neue Klausel erzeugt, die eine Folge davon ist. da bei jedem Schritt mehrere solcher Paare verfügbar sein können, muss der Algorithmus eines auswählen; Diese Wahlmöglichkeiten wirken sich auf die Länge des Beweises aus.

Der erste Punkt wird berücksichtigt, indem die Größe eines Formel-Beweises mit der Größe der Formel verglichen wird. Dieser Vergleich wird unter Verwendung der üblichen Annahmen der rechnerischen Komplexität durchgeführt: Erstens bedeutet ein Verhältnis der Polynom-Beweisgröße / Formelgröße, dass der Beweis eine der Formel ähnliche Größe hat; Zweitens wird dieses Verhältnis im asymptotischen Fall mit zunehmender Größe der Formel untersucht.

Der zweite Punkt wird berücksichtigt, indem für jede Formel der kürzest mögliche Beweis berücksichtigt wird, den die betrachtete Methode liefern kann.

Die Frage der Polynomialität von Beweisen ist, ob eine Methode immer einen Größennachweis eines Polynoms in der Größe der Formel erzeugen kann. Wenn es eine solche Methode gibt, wäre NP mit coNP gleichzusetzen. Aus diesem Grund wird die Frage der Polynomialität von Beweisen für die Komplexität der Berechnungen als wichtig erachtet. Für einige Methoden wurde die Existenz von Formeln bewiesen, deren kürzeste Beweise immer Superpolynom sind. Für andere Methoden ist dies eine offene Frage.

Vergleich der Beweisgröße [ edit ]

Eine zweite Frage zur Komplexität von Beweismitteln lautet, ob eine Methode effizienter ist als eine andere. Da die Prüfgröße von der Formel abhängt, ist es möglich, dass eine Methode einen kurzen und nur eine lange Formel einer anderen Formel ergibt, während eine zweite Methode genau das gegenteilige Verhalten haben kann. In diesem Zusammenhang werden auch die Annahmen verwendet, die Größe der Beweise relativ zur Größe der Formel zu messen und nur die kürzesten Beweise zu berücksichtigen.

Beim Vergleich zweier Beweismethoden sind zwei Ergebnisse möglich:

Für jeden Beweis einer Formel, die mit der ersten Methode hergestellt wurde, gibt es einen Beweis für eine vergleichbare Größe derselben Formel, die mit der zweiten Methode hergestellt wurde.
gibt es eine Formel, so dass die erste Methode einen kurzen Beweis erzeugen kann alle Beweise, die durch die zweite Methode erhalten werden, sind durchweg größer.

Mehrere Beweise der zweiten Art beinhalten widersprüchliche Formeln, die die Negation des Pigeonhole-Prinzips ausdrücken, nämlich $. displaystyle n + 1}$ Tauben passen ${ displaystyle n}$ n "/> Löcher ohne Loch mit zwei oder mehr Tauben.

Automatisierbarkeit [ edit ]

Eine Beweismethode ist automatisierbar, wenn einer der kürzeren Nachweise einer Formel immer in einem Zeitpolynom (oder Subexponential) in der Größe von generiert werden kann der Beweis. Einige Methoden, aber nicht alle, sind automatisierbar. Die Ergebnisse der Automatisierbarkeit stehen nicht im Widerspruch zu der Annahme, dass die Polynom-Hierarchie nicht kollabiert. Dies wäre der Fall, wenn ein Polynom in Zeitgröße (19459037) der Formel immer möglich wäre.