Beweisbarkeit von P=NP

11.06.2010, 11:31	gitterrost4	Auf diesen Beitrag antworten »
Beweisbarkeit von P=NP Hallo, Heute kam in einer Vorlesung eine Frage zur Beweisbarkeit von $\begin{eqnarray} P=NP \end{eqnarray}$ auf. Ich bin folgender Meinung: Sei $\begin{eqnarray} X\ NP \end{eqnarray}$ -Vollstaendig. Angenommen $\begin{eqnarray} P=NP \end{eqnarray}$ ist nicht Beweisbar. Dann kann es keinen polynomiellen Algorithmus $\begin{eqnarray} A \end{eqnarray}$ geben, der $\begin{eqnarray} X \end{eqnarray}$ loest. (Gaebe es ihn koennte man ihn angeben, damit waere $\begin{eqnarray} P=NP \end{eqnarray}$ bewiesen). Da es keinen polynomiellen Algorithmus $\begin{eqnarray} A \end{eqnarray}$ gibt, der $\begin{eqnarray} X \end{eqnarray}$ loest, folgt nun $\begin{eqnarray} P\neq NP \end{eqnarray}$ . Dies ist ein Widerspruch zur Annahme, dass $\begin{eqnarray} P=NP \end{eqnarray}$ nicht beweisbar ist. Ist diese Argumentation stichhaltig? Ist irgendwo ein Fehler? Gruss, gitterrost4
11.06.2010, 11:49	papahuhn	Auf diesen Beitrag antworten »
RE: Beweisbarkeit von P=NP Mit "nicht beweisbar" meinst du unentscheidbar im Sinne der Prädikatenlogik, nehme ich an. Wenn man Turingmaschinen prädikatenlogisch formuliert und tatsächlich Unentscheidbarkeit vorliegen sollte, dann gibt es logische Modelle, in denen P = NP gilt, und andere, in denen P = NP nicht gilt. Im letzten Fall gibt es natürlich Gegenbeispiele, sie sind aber durch das Axiomsystem nicht greifbar, da sie andernfalls in allen Modellen existieren müssten. Du kannst mal in [1] stöbern, dort stehen sehr viele interessante Dinge zu dem Thema. [1] http://www.joergresag.privat.t-online.de/mybk3htm/start3.htm
11.06.2010, 15:45	gitterrost4	Auf diesen Beitrag antworten »
Danke fuer die Antwort! Ich werd mich da mal durchlesen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »