Beweis P vs NP Problem? |
| 10.02.2012, 10:46 | absolutanon | Auf diesen Beitrag antworten » | ||||
Beweis P vs NP Problem?
Ich meine das bekannte P vs NP Problem gelöst zu haben, sprich bewiesen zu haben, dass es nicht effizient lösbar ist. Das Dokument hab ich bei meinen Google Docs freigegeben: https://docs.google.com/viewer?a=v&pid=e...2VhNjIwZTM3Yjdk Falls es nötig ist, übersetze ich es euch auf Deutsch. Wäre froh wenn ihr mir Feedback geben könnt, ob sowas für Mathematiker auch als Beweis gilt, bzw ob der Weg nachvollziehbar ist. Ich bin selbst noch Student(nicht Mathematik 
)Danke im Voraus! |
||||||
| 10.02.2012, 10:58 | Airblader | Auf diesen Beitrag antworten » | ||||
Und wie kommt es zu dieser Behauptung? Und überhaupt finde ich das ganze Vorgehen unverständlich. Du schreibst zwei Seiten über ein selbstgestelltes Problem, was in zwei Zeilen gepasst hätte. Was dieses "Problem" nun mit P, NP oder irgendeiner anderen Komplexitätsklasse zu tun hat ist ebenfalls unklar. Und dann kommt es plötzlich zu obiger Behauptung. Nicht, dass du nicht deinen Spaß haben sollst, aber ich kann mit Zuversicht sagen, dass du mit ein paar Oberstufenüberlegungen nicht eines der größten, ungelösten Probleme der Mathematik / Theoretischen Informatik lösen können wirst. Schon allein solche Ergebnisse legen dies nahe, ganz zu schweigen von der Tatsache, dass es unvorstellbar scheint, dass kein Mathematiker bisher auf die Lösung gekommen wäre, wäre sie denn so einfach. air |
||||||
| 10.02.2012, 11:14 | absolutanon | Auf diesen Beitrag antworten » | ||||
Das Problem dass ich hier beispielhaft anführe ist eben eines aus der Klasse NP: Das heist es ist leicht die Lösung zu validieren, aber die Frage ist, ob die Lösung zu finden ebenfalls effizient möglich ist. Falls eines der Probleme aus dieser Klasse NP gelöst ist, bedeutet dies, dass auch alle anderen Probleme in der Klasse gelöst werden können. (Dies wurde schon bewiesen. Und das ist auch der Grund warum das Problem als so wichtig klassifiziert worden ist, weil Probleme mit dieser Struktur in unterschiedlichsten Bereichen immer wieder auftauchen)) Ich habe also eines dieser Probleme aus NP ausgewählt, in dem Fall das Subset Sum Problem, da es sehr schnell von jedem verstanden werden kann. Das Hintergrundwissen für den Zusammenhang vom Subset Sum Problem und NP hab ich fälschlicher Weise vorausgesetzt. Mit dem aufgestellten Gleichungssystem schaffe ich eine 1:1 Beziehung zwischen Problem und Gleichung: 1. Wenn die Gleichung effizient gelöst werden kann, kann das Problem effizient gelöst werden. (Einsprüche?) 2. Die Gleichung kann nicht effizient gelöst werden, weil dafür eine Funktion nötig wäre, welche zwei gültige Werte für eine Inputvariable zurückgibt. Dies ist per Definition nicht möglich. |
||||||
| 10.02.2012, 11:23 | absolutanon | Auf diesen Beitrag antworten » | ||||
In dem du das angesprochene Gleichungssystem zu lösen versuchst, wirst du sehen dass das Auflösen der Gleichung validation(B)=0 nach B zwei Lösungen hat. Hier liegt der Knackpunkt des Problems, die zwei Lösungen lassen sich nicht in eine Variable packen. |
||||||
| 10.02.2012, 11:33 | galoisseinbruder | Auf diesen Beitrag antworten » | ||||
Das ist kein Beweis sondern nur eine Behauptung. Wieso fallen denn z.B. die zwei Lösungen nicht zusammen? Mal ganz abgesehen davon, dass ich keine Ahnung hab was in eine Variable packen heißen soll. Aber eine deutlich größeres Problem ist folgendes: Das ist nicht das Subset sum problem was du hier betrachtest, sondern nur ein ganz speziell enfacher Fall. Kannst du mir von der Menge sagen, ob man 3567 als Summe von einigen der Elemente der Menge schreiben kann? Das ist auch ein Subset sum problem. Dein verfahren tut´s nicht. |
||||||
| 10.02.2012, 11:40 | Airblader | Auf diesen Beitrag antworten » | ||||
Ich weiß durchaus, was das P-NP-Problem und Komplexitätsklassen sind, auch wenn ich Komplexitätstheorie nur als Einzelvorlesung gehört habe. Das Problem mit den zwei Funktionswerten kann man aber sehr einfach umgehen, indem man die Funktion auf einem Produkt von Mengen definiert -- da hast du deine zwei Werte; das ist ja auch ein typischer Trick, wenn man zum Beispiel Mehrband-Turingmaschinen auf 2-Band-Turingmaschinen reduzieren will. Außerdem hängt es daran, dass, wenn ich dir das alles mal glaube, du lediglich die Lösung, die du bastelst, als nicht in P verifizierst. Dass es nicht auf anderem Weg möglich ist, das Problem zu lösen, bliebe zu zeigen. Ich halte daran fest, dass ich jede Wette eingehen würde, dass der Beweis in der Fachwelt auf wenig Beifall stoßen würde -- trotz meines beschränkten Komplexitätstheorie-Wissens. Lies dir mal die Diskussionen zum Beweisversuch von vor ein paar Monaten durch und überlege dir, ob du wirklich der Meinung bist, eine kleine quadratische Gleichung könne die Lösung sein. Just saying.
Edit: Nicht, dass ich sagen will, dass man es nicht versuchen kann. Eine kurze und einfache Lösung heißt ja nicht zwangsweise, dass sie falsch ist. Es sollte lediglich zum selbstkritischen Nachdenken anregen. Es gibt gute Gründe, warum sich die Fachwelt darüber den Kopf zerbricht. air |
||||||
| Anzeige | ||||||
|
|
||||||
| 10.02.2012, 12:18 | absolutanon | Auf diesen Beitrag antworten » | ||||
Eine Funktion f(x) welche für zwei unterschiedliche x die gleichen y Werte liefert, kann nicht in EINE Funktion y(x) transformiert werden. Beispiel: y=x^2...eine Funktion welche die obige Bedingung erfüllt...von dieser möchte ich jetzt aber beide Lösungen der X-Variable in einen AUSDRUCK packen, das kann aber nicht funktionieren, weil die Lösungen wären x = wurzel(y) UND x = -wurzel(y) ...womit wir wieder beim Knackpunkt wären. Die Gleichung kann nicht effizient gelöst werden. Selbst wenn der "Rest" des Gleichungssystems unendlich schnell gelöst werden kann, das Bottleneck wäre immer alle Lösungen durchprobieren zu müssen.
Ich hab absichtlich wegen schneller Verständlichkeit ein EINFACHES und KONKRETES Beispiel gewählt. Die allgemeine Formulierung hätte ich natürlich auch verwenden können. Wenn man die Gedanken weiter spinnt kommt man drauf dass das selbe Problem wie bei dem einfachen praktischen Beispiel auch bei jedem anderen Subset Sum Problem immer wieder auftritt. @Airblader: das hört sich interessant an, muss zunächst genauer recherchieren(hab davon bis jetzt noch nichts gehört). werde eventuell erst nachmittags/abends antworten können. |
||||||
| 10.02.2012, 12:26 | Airblader | Auf diesen Beitrag antworten » | ||||
Kleine Ergänzungsfrage bzw. ein Vorschlag: Ich gehe davon aus, dass du Informatik studierst. Schnapp dir doch einen Ausdruck deines Papers und lege es einem Komplexitätstheorie-Professor nach der Vorlesung auf den Tisch. Da es nur zwei Seiten sind, kann er es direkt vor Ort lesen. air |
||||||
| 10.02.2012, 12:32 | galoisseinbruder | Auf diesen Beitrag antworten » | ||||
Nur weil zwei Terme unterschiedlich aussehen sind sie noch lange nicht verschieden.
Das zeigt eindeutig dass du keine Ahnung hast was du tust. Den Gedanken weiterzuspinnen wäre deine Aufgabe im Beweis denn das ist hier der entscheidende Schritt. Das Problem beim Subset sum Problem ist ja nicht dass es nicht lösbar wäre(geht durch Probieren aller Lösungen) sondern dass der benötigte Rechenaufwand, abhängig von der Größe der Menge, exponentiell wächst. Um in P zu sein müsstest du zeigen, dass man das schneller berechnen kann. Und dafür langt ein Beispiel halt einfach gar nicht. (und wenn sich dein Algorithmus so einfach anpassen lassen würde hättest du mein gestelltes problem doch schon lange gelöst.) Ach ja: Ich bin nicht schwerhörig, man muss mich nicht anschreien. |
||||||
| 10.02.2012, 13:10 | gonnabphd | Auf diesen Beitrag antworten » | ||||
Hi, Wie schon mehrmals gesagt: Dein "Beweis" ist kein Beweis. Aber wen du dich für Algorithmen und Komplexität interessierst, dann könntest du dich ja trotzdem ein bisschen intensiver damit auseinandersetzen. Ich kenne mich nicht wirklich mit dem Gebiet aus, aber Introduction to Algorithms ist ein sehr gut geschriebenes Buch zur Einführung. Komplexitätstheorie ist darin zwar kein Schwerpunkt, aber wird ebenfalls angeschaut. Ich sage das vor allem, da ich davon ausgehe, dass du denkst, es sei mehr oder weniger offensichtlich, dass man beim Subset-Sum Problem alle möglichen Lösungen durchtesten muss. Doch wenn du dir das Buch oben durchschaust, dann wirst du entdecken, dass es viele Probleme gibt, welche durchaus so wirken als könnte man sie nicht effizient lösen, für welche man aber doch einen cleveren, polynomiellen Algorithmus gefunden hat (gerade von der Technik des dynamischen Programmierens war ich in manchen Situationen sehr beeindruckt).
p.s.: Es kann Spass machen, sich an schwierigen Problemen zu versuchen. Und man sollte natürlich auch herausfinden, woran die eigenen Ideen denn nun scheitern. Aber allzu viel Zeit würde ich damit nicht verbringen, da man sich als Laie ziemlich sicher sein kann, dass man keine Lösung finden wird (ausser vielleicht, wenn man sich enorm viel Wissen selbst angeeignet hat - was allerdings unwahrscheinlich ist). |
||||||
| 10.02.2012, 13:28 | Airblader | Auf diesen Beitrag antworten » | ||||
Zu seiner Verteidigung, zwei, drei Wörter in Versalien würde ich als Auszeichnung auffassen, nicht als anschreien.
air |
||||||
| 10.02.2012, 14:00 | Mazze | Auf diesen Beitrag antworten » | ||||
Das P-NP Problem wurde ja schon oft zerpflückt. Es gibt Beweise die über 100te Seiten gehen und trotzdem falsch waren. Daher muss man verstehen, dass man von vornherein skeptisch an diese Sache geht, wenn die vermeindliche Lösung online in einem Forum diskutiert wird, anstatt sie in einer Fachzeitschrift zu veröffentlichen. Deine Argumentation zumindest ist nicht schlüssig. Du erbringst den Beweis , dass es keine andere Möglichkeit gibt, dass Problem effizient zu lösen nicht. Du sagst lediglich, dass dein Weg zu keiner effizienten Lösung führt, und das wird auch nicht streng bewiesen, sondern an einigen Stellen mit unbewiesenen Aussagen gerechtfertigt. Grundsätzlich find ichs aber auch gut und sinnvoll sich an schwierigen Problemen zu probieren. Es gibt durchaus Beispiele in der Geschichte wo Laien sinnvolle Beiträge zur Wissenschaft lieferten. Nur gerade als Laie sollte man sich auch klar darüber sein, dass man solche weltbewegenden Resultate eventuel von Profis gegenchecken lassen sollte. Wie oben schon vorgeschlagen, zeigs doch mal nem Prof für theoretische Informatik oder so
. |
||||||
| 10.02.2012, 14:34 | absolutanon | Auf diesen Beitrag antworten » | ||||
Falls du unter "auf ein Produkt von Mengen definieren" Faktorisierung verstehst, möchte ich festhalten, dass dies das ursprüngliche Problem nicht löst. Nehmen wir wieder die funktion y=x^2 Gesucht sei die Lösung nach x....wobei x ein Ausdruck sein soll, aber kann man mathematisch die Lösungen x=+wurzel(y) und x=-wurzel(y) nicht in eine Funktion unterbringen, auch nicht wenn man faktorisiert: y = x*x. Eine quadratische Funktion ist nur eine von unendlich vielen möglicher Funktionen zur validierung der boolschen variablen und dient der Einschränkung auf Werte 0 oder 1. Das verlangt nach einer Funktion/Relation welche bei einem Input zwei Outputs generiert. Wie soll das funktionieren? Ich habe mich die letzten Sommerferien mit dem Problem auseinandergesetzt und mir ist klar, warum es keinen effizienten Algorithmus zur Lösung geben kann. Nun war meine Idee, damit die "Mathematiker" auch meine Erkenntnis nachvollziehen können, das Problem in ein mathematisches Problem zu transformieren und zu zeigen dass dieses mathematische Problem(Gleichungssystem) nicht effizient lösbar ist. @galoisseinbruder Ich wollte nicht offensiv wirken nur betonen. @Allgemein Naja, dann sehen wir mal ob es jemand anders jemals beweisen kann. Die Nachvollziehbarkeit eines solchen Beweises scheint die wahre Schwierigkeit zu sein. Danke für die schnellen Antworten, mal sehen wie sich die Sache weiter entwickelt, eventuell werde ich mal mit meinem Professor darüber sprechen. |
||||||
| 10.02.2012, 19:10 | Airblader | Auf diesen Beitrag antworten » | ||||
Oder aber du denkst das nur. Schnappe dir einen Professor.
Zum Produkt: Ich hatte auf Turingmaschinen hingewiesen, damit du dort ggf. nachschlagen kannst (du bist ja Student, oder?). Bei einem derart wichtigen Thema wäre das doch eigentlich lohnenswert für dich. Aber dann bin ich mal nicht so: mit wäre eine Funktion, die mit einem Input zwei Outputs generiert. Und solche Tupel fasst man dann als einzelne Objekte auf. Absolut kein Problem. air |
||||||
| 15.02.2012, 12:38 | absolutanon | Auf diesen Beitrag antworten » | ||||
Ja, was du hier machst, du definierst dir selbst eine Funktion die die geforderten Eigenschaften erfüllt. Um allerdings dann die konkreten Funktionswerte für die Problemlösung zu errechnen, muss man erst wieder beide möglichen Funktionswerte pro bool'scher Variable evaluieren. Es reduziert als nicht die Komplexität des Problemes. Ich fasse also noch mal zusammen: Mit dem aufgestellten Gleichungssystem schaffe ich eine 1:1 Beziehung zwischen Problem und Gleichung: 1. Wenn die Gleichung effizient gelöst werden kann, kann das Problem effizient gelöst werden. 2. Die Gleichung kann nicht effizient gelöst werden, weil dafür eine Funktion nötig wäre, welche zwei gültige Werte für eine Inputvariable zurückgibt. Dies ist per Definition nicht möglich. 3. Dadurch dass ich zeige, dass die Gleichung nicht effizient gelöst werden kann zeige ich, dass auch das Problem nicht effizient gelöst werden kann. Denn wenn das Problem durch IRGENDEINEN anderen Algorithmus gelöst werden könnte, würde das bedeuten, dass auch die Gleichung mit diesem Algorithmus effizient gelöst werden könnte. |
||||||
| 15.02.2012, 13:04 | Airblader | Auf diesen Beitrag antworten » | ||||
Für den Beweis eines Problems dieser Größenordnung hattest du nun genügend Zeit, die Lösung einem Professor für Theoretische Informatik vorzulegen. Was hat der dazu gesagt? air |
||||||
| 15.02.2012, 15:46 | tmo | Auf diesen Beitrag antworten » | ||||
Tja, das machen Mathematiker halt so
Sie lösen ihre Problem durch geschickte Definitionen.Und so wie ich das sehe wollte Airblader hier gar nicht das P-NP-Problem lösen, schon gar nicht einen Algorithmus angeben um NP-Probleme effektiv zu lösen, sondern dir einfach nur demonstrieren, dass du zu wenig Kenntnisse der Mathematik hast, um solch ein Problem zu lösen. Es kommt zwar aus der theoretischen Informatik, die aber bekanntlich ohne Mathematik nicht auskommt. Selbst wenn das alles richtig wäre, was du da erzählst, so machst du einen entscheidenen (Anfänger-)Fehler. Du hast Problem A und Problem B. Dann sagst du, wenn ich A lösen kann, kann ich auch B lösen. Dann sagst du, du kannst aber A nicht lösen. Und daraus folgerst du, dass du auch B nicht lösen kannst. Das ist schlichtweg eine nicht zugelassene Folgerung. Was du in dem "Beweis" eigentlich machst: Du formulierst die triviale Lösung - nämlich systematisches Ausprobieren - einfach etwas um und sagst dann, dass die Komplexität immer noch NP ist. Das verwundert niemanden, ist aber leider noch nicht mal im Ansatz eine Idee, wie man denn zeigen könnte, dass es wirklich gar keine Möglichkeit gibt, das Problem in polynomieller Zeit zu lösen. |
||||||
| 17.02.2012, 10:30 | absolutanon | Auf diesen Beitrag antworten » | ||||
Nein, ich formuliere nicht eine Lösung um, sondern ein Problem und zeige dann dass das Problem nicht effizient gelöst werden kann. |
||||||
| 17.02.2012, 11:11 | Mazze | Auf diesen Beitrag antworten » | ||||
Wenn Du dir so sicher bist stelle deine Lösung doch deinem Professor vor, oder schreib gleich ans Nature Magazin, ich denke mal die P-NP Problem Lösung dürfte es da locker aufs Cover schaffen. Dein Beweis passt ja auf 2 Seiten, da drucken die den sicher und die Fields Medaille dürfte dir auch sicher sein (ich zähle theoretische Informatik zur Mathematik
), ansonsten gibts sicher den Turing-Award. Ganz im Ernst, das was Du vorstellst ist nicht im Ansatz ein Beweis. Es haben Dir jetzt schon einige die Gründe dafür dargelegt , aber Du scheinst diese konsequent zu ignorieren oder einfach nicht zu verstehen. Ich finde es ohne merkwürdig dass eine Lösung für so ein Problem erst in einem Forum online diskutiert wird, statt mit der entsprechenden Expertise an den Universitäten. Unsere Argumente lehnst Du doch ab, warum sprichst Du nicht mit den Profs. darüber ? |
||||||
| 17.02.2012, 17:21 | absolutanon | Auf diesen Beitrag antworten » | ||||
Ich habe mich entschlossen meinen Professor damit nicht zu "belästigen". Nachdem bei euch Forumteilnehmern wohl einige "richtige" Mathematiker oder -Studenten dabei waren und dies nicht als Beweis akzeptieren - denke ich, dass auch der Professor mit ähnlichen Gegenargumenten wie ihr kommen würde. Bin wirklich schon neugierig wann das Problem wirklich mal bewiesen wird... Eines kann ich euch versichern, das Resultat wird sein: P != NP Bis dahin, denke ich wir sollten die Diskussion aufgeben, es sei denn ihr wollt die Diskussion fortführen, schau vielleicht alle paar Monate mal rein
Wenn ich mal einen Prof in einer geeigneten Situation treffe, werde ich ihn fragen. Soweit, danke für all eure Antworten und Bemühungen! |
||||||
| 01.02.2015, 07:56 | Kramer | Auf diesen Beitrag antworten » | ||||
| RE: Beweis P vs NP Problem? Der Thread ist ja nun schon 3 Jahre alt. Trotzdem, falls du das hier liest würde ich dich darum beten, deine Arbeit nochmal zu reuppen. Interessiert mich auf was du da gekommen bist. |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
