Projekt:Beweis für P ungleich NP von Thomas Käfer

 Info: Dies ist ein Projekt mit originärer Forschung.

Beweis für $P\neq NP$

Zusammenfassung

Es wurde lange diskutiert, ob zwischen $NP$-Probleme und $P$-Problemen eine Unterscheidung besteht. Das lässt sich mithilfe der Strengen Logik beweisen. Es ergibt sich, dass $NP$-Probleme in der Reinen Logik eine Entsprechung der Angewandten Logik haben.

Einführung

Zur Einführung wird kurz erklärt, was die Strenge Logik ist und die Behandlung des Modus ponens darin dargestellt.

Allgemeines zur Strengen Logik

Die Strenge Logik wurde von Walther Brüning 1996 in seinem Buch Grundlagen der Strengen Logik begründet. Dem Vorwort ist zu entnehmen, wie sie aufzufassen ist. Sie benötigt für ihren Aufbau lediglich das Prinzip der Identität und das Prinzip der Limitation, sowie die Bejahung ($A$) und die Verneinung ($N$).

Das Prinzip der Identität formuliert er (positiv) so: "Jedes in der Logik Festgesetzte ist mit sich selbst und nur mit sich selbst identisch."

Das Prinzip der Limitation formuliert er (positiv) so: "Jedes Festgesetzte ist

1. von den anderen
2. aber auch nur von den anderen

limitativ unterschieden."

Für eine genauere Erläuterung der Prinzipien, siehe das Buch (Seite 58f).

"Verletzt eine Logik die Prinzipien, so heißt sie transgressiv." (Seite 50).

"Beim Rückgang zum Anfang des logischen Denkens" geht Brüning von der dyadischen Stufe (zwei Sachverhalte betreffend) zur henadischen Stufe (einen Sachverhalt betreffend) zurück. Hier soll zunächst die henadische Stufe erklärt werden (Seite 52f):

Henadisch bedeutet genau ein Sachverhalt wird betrachtet. Durch die logischen Prinzipien wird ein Grundbereich aufgespalten in zwei Teilbereiche (für eine genauere Erläuterung, siehe das Buch). Es entsteht ein Sachverhaltsbereich (Bereichsbezeichnung: $B$) und ein Komplement von $B$ (Bereichsbezeichnung: ~$B$). Aufgrund der logischen Prinzipien können diese Teilbereiche kombinatorisch vier Möglichkeiten annehmen:

Henadische Stufe

	$B$	~$B$
1	$A$	$A$
2	$N$	$N$
3	$A$	$N$
4	$N$	$A$

Dies sind jeweils synthetische Festsetzungen. Zu beachten ist, dass es formallogisch keinen Vorrang affirmativer vor negativer Geltung gibt.

"Die vier vollständigen henadischen Formeln stehen miteinander im Widerspruch. An mindestens einer Stelle treffen je zwei Formeln $A$ und $N$ aufeinander:

Lässt man unvollständige Formeln zu ($Au$, $uA$, $Nu$, $uN$), so kann man hier schon eine Vorform logischer Ableitung aufzeigen. Logische Ableitung im strengen Sinn heißt ja, aus einer vorgegebenen Information einen Teil herauslösen.

Z. B. ist $AN$ vorgegeben, so folgt daraus logisch $Au$:

$AN$ → $Au$

[…]."

Analog kann man bei weiteren Formeln vorgehen. Das sind Beispiele für unmittelbare Schlüsse.

Weiters:

"Aus der Annahme

Es gibt keine Nicht-Menschen ($uN$)

folgt nicht:

Es gibt Menschen ($Au$)

[…]."

Nun kann man die Festsetzung der ersten Teilung des Grundbereichs (die zur henadischen Stufe führte) erweitern.

"Bei einer ersten Erweiterung werden vier Affirmationen bzw. Negationen gleichzeitig verwendet. Dadurch wird der Grundbereich noch einmal geteilt und entsprechend ein neuer Sachverhalt samt Komplement ($C$, ~$C$) eingeführt. Es ergibt sich die dyadische Stufe.

Zwischen der ersten Sachverhaltsebene ($B$, ~$B$) und der zweiten ($C$, ~$C$) bestehen vier Überschneidungsmöglichkeiten (die ihren Ausdruck in den entsprechenden Geltungswertstellen finden) […]."

Analog zur monadischen Stufe ergeben sich 16 mögliche vollständige Sachverhaltsverbindungen.

"Analoge Erweiterungen können dann beliebig angefügt werden[.]

[…]

Es ist bei all dem Gesagten darauf zu achten, daß es sich hier im Bereich der Reinen Logik immer um Sachverhalte allgemeiner Natur handelt. Individuelle Sachverhalte werden erst in der Angewandten Logik berücksichtigt."

Es kann zwischen Stufen oder innerhalb von Stufen geschlossen werden. Zum Schließen (hier und im Folgenden hauptsächlich auf derselben Stufe) ist Folgendes zu sagen (siehe das Buch, Seite 21ff): Der Übergang zu mittelbaren Schlüssen erfordert die Einführung eines zweiten Begriffs. Dazu: "Die Geltungswertformeln sind entsprechend zu verlängern[.]" Es entstehen Gleichstellen die im Weiteren mit Kleinbuchstaben belegt werden. Weiters (siehe das Buch, Seite 23): "Wie für das unmittelbare Schließen gilt auch für das mittelbare:

Eine logische Folgerung im strengen Sinne ist das Herauslösen eines Teilaspekts (Konklusion) aus einer vorgegebenen Information (Prämissen). Was dazu gebraucht wird, ist nur die Vorgabe der Information und das Prinzip der Identität."

Der Schluss soll aus einer vorgegebenen Information den Teil herauslösen, der für die Konklusion relevant ist. Weiters dazu: "Dabei werden die Gleichstellen der erwarteten Konklusion […] im Hinblick auf mögliche Information aus den Prämissen durchgesehen, und so wird schrittweise die Formel der Konklusion aufgebaut[.]"

"Das […] Schlußverfahren kann auf die folgenden beiden Regeln zurückgeführt werden:

1. Ist von zwei $a$-Gleichstellen der Prämissen eine blockiert (durch ein $n$ der anderen Prämisse), so muß das $a$ der anderen Gleichstelle in die Konklusion eingehen (Die entsprechenden Gleichstellen der Konklusion sind also $a$).
2. Sind zwei Gleichstellen der Konklusion von den Prämissen her durch mindestens ein $n$ blockiert, so müssen sie auch in der Konklusion beide $n$ sein.

Die leitende Grundfrage bei dem Verfahren ist einfach: Welche Information der Prämissen ist für die Konklusion relevant." (siehe das Buch, Seite 26f)

Wenn beide Regeln gleichzeitig (bei bestimmten Gleichstellen der Konklusion) angewandt werden müssten, ständen die Prämissen im Widerspruch zueinander (siehe dazu das Buch, Seite 88).

Bedingungsschlüsse und Modus ponens als Beispiel in der Strengen Logik

Allgemeines

Das angegebene Schlussverfahren kann auf den Modus ponens angewandt werden:

"In den verschiedenen Abschnitten der strengen Speziellen Logik werden jeweils einige zusätzliche Aspekte herausgestellt, die sich in dem entsprechenden Zusammenhang als besonders nützlich erweisen.

Das ist zum Beispiel der Fall bei den Bedingungsschlüssen der Prädikatenlogik […].

Es ist aber wichtig zu sehen, daß alle diese Aspekte grundsätzlich für die gesamte Reine Logik Gültigkeit haben. […]" (siehe das Buch, S.100)

Bedingungsschlüsse

"Die Bedingungen, von denen die Schlüsse hier ausgehen, sind in Sachverhaltsverbindungen formuliert, deren Geltungswertformeln neben Unbestimmtheitszeichen nur $N$ enthalten." (siehe das Buch, Seite 104).

Modus Ponens

Die erste Prämisse ist eine Bedingung dyadischer (d. h. zwei Sachverhalte sind miteinander verbunden) Stufe (deshalb Großbuchstabe). Es handelt sich um einen Bedingungssatz (Es gibt kein $F$ ohne $G$.). Die zweite Prämisse ist eine dyadisch verlängerte henadische (d. h. einen Sachverhalt betreffend) Formel (deshalb Kleinbuchstaben und Gleichstellen); ebenso die Konklusion. (Das fett geschriebene $a$ geht in die Konklusion ein, weil das andere $a$ der Gleichstelle von einem $N$ blockiert wird.). Das hochgestellte $c$ bedeutet condicio (siehe v. a. Seite 106):

Modus Ponens in der Strengen Logik

	F G	~F G	F ~G	~F ~G
$F\supset ^{c}G$	u	u	N	u
$F$	a	u	a	u
$G$	a	a	u	u

Die Spalten sind nach den verschiedenen möglichen Kombinationen getrennt. Die Verlängerung der Geltungswertformeln der Prämisse $F$ bzw. der Konklusion $G$ ergibt sich durch die Einführung des jeweils zweiten Begriffes $G$ bzw. $F$. Ihr Wert bleibt deshalb bei der Erweiterung gleich (es bilden sich Gleichstellen). $a$ – kurz für Affirmation (entspricht wahr); $N$ – kurz für Negation (entspricht falsch); $u$ – kurz für unbestimmt; ~$X$ – kurz für Komplement von $X$.

Das wäre also ein Beispiel für einen Bedingungsschluss.

Umschreibungen

$P$-Probleme

$P$-Probleme können mit der Puren Logik so umschrieben werden:

$P$-Probleme

	F G	~F G	F ~G	~F ~G
$F$ und ~$F$ nicht	a	n	a	n
$F\cap ^{c}G$	u	N	N	u
$G$ und ~$G$ nicht	a	a	n	n
Ganzformel	A	N	N	N

Sie sind also bidirektional (Genauso gut könnte man von $G$ und ~$G$ auf $F$ und ~$F$ schließen.). Ganzformeln fassen die (relevante) Information auf einer höheren Stufe zusammen.

Umschreibung von $P$-Problemen in der Angewandten Logik

Dazu schreibt Brüning: "In der Angewandten Logik kann die Geltung individueller Sachverhalte zunächst im Sinne von bloßen 'Existenz'-Bestimmungen eingeführt werden. Wird eine $A$-Stelle durch einen e-Index zusätzlich bezeichnet ($A^{e}$), so soll damit gesagt sein, daß die Stelle nicht nur 'offen' ist, sondern daß hier auch Individuen (in unbestimmter Zahl) 'existieren'. Dabei ist 'Existenz' im Sinne logischer Festsetzung verstanden. Es geht hier nicht um Aussagen über real Bestehendes.

In gewissen überschaubaren Zusammenhängen kann die e-Indizierung auch einfach dadurch ersetzt werden, daß man alle $A$-Stellen als existentiell bestimmt versteht." (Seite 162)

$NP$-Probleme

Umschreibung von $NP$-Problemen

Bei $NP$-Problemen (Entscheidungsprobleme) hingegen ist bekannt, dass die Lösung ein individueller Sachverhalt ist (z. B. $SAT$-Problem: Es gibt mindestens eine Belegung [Erfüllbarkeit]). Es handelt sich also um Angewandte Logik und um einen indviduellen Sachverhalt. Hier soll er $g^{i}$ heißen. Die Geltungswertformel heißt damit $A^{i}A^{i}$. D.h. Bei individuellen Sachverhalten kann nur eins der $A^{i}$ zu $A$ werden und die restlichen $A^{i}$s werden dann zu $N$s (Siehe Seite 164ff und Seite 109ff. Ein individueller Sachverhalt kann nicht geteilt werden.). Dass beide $A^{i}A^{i}$ zu $N$ werden, stellt keinen Widerspruch dar ($NN$, ebd.). Beim Schließen bleiben die $A^{i}$s immer zusammen (ebd.).

Als Prämisse bei $NP$-Problemen gilt, dass zusätzlich zu einem Bedingungssatz $F\supset ^{c}G$ ($uuNu$), auch ein verifier $F\subset ^{c}G$ ($uNuu$) vorhanden sein muss. Daraus ergibt sich als Bedingungssatz: $F\cap ^{c}G$ ($uNNu$).

Zunächst ist ohne Bedeutung, ob $F\supset ^{c}G$ ($uuNu$) oder $F\subset ^{c}G$ ($uNuu$) als verifier interpretiert wird, weil beide transitiv, aber nicht symmetrisch sind. Bei "Festsetzung bestimmter Bedeutungen für die Begriffe" ist aber auf eine Unterscheidung zu achten (Es entsteht ein anderer Schlusszusammenhang, Seite 43).

Zuerst wird mit dem Bedingungssatz $F\supset ^{c}G$ ($uuNu$) geschlossen. Wie schon erwähnt müssen $A^{i}$-Stellen beim Schließen zusammenbleiben. Deshalb folgt entweder $g^{i}$ ($A^{i}A^{i}$) oder $f^{i}$ ($A^{i}A^{i}$):

Erster Schritt von $NP$-Problemen

	F G	~F G	F ~G	~F ~G
$f^{i}$	$(a^{i})$	$a^{i}$	$a^{i}$	$(a^{i})$
$F\supset ^{c}G$	u	u	N	u
Entweder:
$g^{i}$	$a^{i}$	$a^{i}$	$a^{i}$	$a^{i}$
Oder:
$f^{i}$	$a^{i}$	$a^{i}$	$a^{i}$	$a^{i}$
Ganzformel	$(A^{i})$	u	N	$(A^{i})$

Jetzt könnte das Problem also schon gelöst sein. Nur könnte man das nicht beweisen. Also wird mit dem verifier $F\subset ^{c}G$ ($uNuu$) noch einmal geschlossen.

Pro Synthese kann man aus verlängerten Individuenvariablen nur einmal schließen.

Es folgt also eine neuerliche Synthese der Prämissen. Je nachdem, ob man die Individuenvariable als diesselbe (idente) anerkennt, ergeben sich zwei Möglichkeiten:

Die erste Möglichkeit soll nun festsetzen, dass sich das Individuum aus der Prämisse nicht ändert (ident):

Zweiter Schritt von $NP$-Problemen mit einem identen Individuum

	F G	~F G	F ~G	~F ~G
$f^{i}$	$(a^{i})$	$a^{i}$	$a^{i}$	$(a^{i})$
Ganzformel	$(A^{i})$	u	N	$(A^{i})$
$F\subset ^{c}G$	u	N	u	u
Ganzformel	$A^{i}$	N	N	$A^{i}$

Es folgt $P\neq NP$. (Verschränkung: Vertrauen kann nicht bewiesen werden.)

Die zweite Möglichkeit soll nun festsetzen, dass sich das Individuum aus der Prämisse ändert (unterschiedlich):

Zweiter Schritt von $NP$-Problemen mit einem unterschiedlichen Individuum

	F G	~F G	F ~G	~F ~G
$f^{i}$zwei	$(a^{i})$	$a^{i}$	$a^{i}$	$(a^{i})$
$F\cap ^{c}G$	u	N	N	u
Ganzformel	$(A^{i})$	N	N	$(A^{i})$

Da wieder nur einmal geschlossen werden kann, folgt $P=NP$. (Souveränität: Vertrauen muss bewiesen werden.)

Exkurs

Da konventionelle Computer die Verschränkung nicht beherrschen, ändern sie das Individuum. Sie können also nur $P$-Probleme schnell lösen (schrittweise Kalkulation). Dabei wird der Bedingungssatz $F\sqcap ^{c}G$ ($uNNN$) verlängert und eine Dummy-Variable $H$ und ~$H$ nicht ($AN$) eingeführt. Sie enthält alle Informationen, die die Individualität ausmachen (z. B. eine Pseudozufallsinformation) und sie von anderen Individuen abtrennt:

Konventionelle Computer können nur $P$-Probleme schnell lösen

	F G H	~F G H	F ~G H	~F ~G H	F G ~H	~F G ~H	F ~G ~H	~F ~G ~H
$F\sqcap ^{c}G$	u	n	n	n	u	n	n	n
$H$ und ~$H$ nicht	a	a	a	a	n	n	n	n
$F$ und ~$F$ nicht	a	n	a	n	a	n	a	n
$G$ und ~$G$ nicht	a	a	n	n	a	a	n	n

Transformation von $NP$-Problemen zu $P$-Problemen

Bekannte Lösungen sind einfach zu überprüfen. Die Ganzformel lautet: '$F$ nur mit $G$ und ~$F$ nur mit ~$G$' ($A^{i}NNA^{i}$). Wenn aus dem gelösten $NP$-Problem $G$ ($Au$) resultiert, folgt weiters (s. S. 113):

Bei resultierendem $G$ kann man $F$ zur Transformation zu $P$-Problemen verwenden.

	F G	~F G	F ~G	~F ~G
$F\cap ^{i}G$	$A^{i}$	N	N	$A^{i}$
$G$	a	a	u	u
$F$	a	u	a	u

Wenn aus dem gelösten $NP$-Problem Nicht $G$ ($G'$, $Nu$) resultiert, folgt alternativ:

Bei resultierendem Nicht $G$ ($G'$) kann man ~$F$ zur Transformation zu $P$-Problemen verwenden.

	F G	~F G	F ~G	~F ~G
$F\cap ^{i}G$	$A^{i}$	N	N	$A^{i}$
Nicht $G$ ($G'$)	n	n	u	u
~$F$	u	a	u	a

Umschreibung von $NP$-Problemen in der Reinen Logik

$A^{i}$s entsprechen in der Reinen Logik $A^{1}$s. ($A^{k}$s stehen für kollektive Sachverhalte in der Angewandten Logik.)

Konklusion

Sofern $NP$-Probleme behauptet (synthetisiert) werden, folgt aus ihnen eine durchschnittlich (wesentlich) längere Laufzeit gegenüber (synthetisierten) $P$-Problemen. Entscheidungsprobleme sind individuelle Sachverhalte. Die längere Laufzeit wird durch die Klarheit über eine Entscheidung abgegolten.

Bisher hatten Bereiche der Logik transgressiven Charakter. Mit Hilfe der Strengen Logik ist zu beweisen:

Rein logisch sind $NP$- und $P$-Probleme unterschiedlich.

Danksagung

Meinen Eltern.