Erklärung P-NP Problem? |
| 05.03.2012, 18:59 | Cheftheoretiker | Auf diesen Beitrag antworten » | ||
| Erklärung P-NP Problem? ich habe folgendes zum dem P-NP Problem gelesen, "Das ''P versus NP''-Problem besteht darin, zu entscheiden, ob jede Sprache, die durch einen nicht-deterministischen Algorithmus in polynomialer Zeit erkannt wird, auch durch einen deterministischen Algorithmus in polynomialer Zeit erkennbar ist. Das Problem ist von inherenter Bedeutung für die Berechnungstheorie, weil seine Beantwortung die Existenz bzw. Nichtexistenz notorischer Berechnungsprobleme impliziert. In dem Proseminar wird auf der Grundlage des Turingschen Berechnungsmodells das Problem formuliert und die NP-Vollständigkeits-Theorie entwickelt, i.e., es werden die Konsequenzen einer negativen Antwort auf das PNP-Problem aufgezeigt. Das Problem ''P versus NP'' gehört zur Liste der sieben Milleniums-Preis-Probleme, welche das Clay-Institut im Mai 2000 in Paris mit einem Preisgeld von jeweils einer Million Dollar ausgelobt hat." Leider verstehe ich ehrlich gesagt garnicht was damit gemeint ist. Könnte mir das Problem wohl mal einer mit etwas einfacheren Worten deutlich machen? Ich habe zum Beispiel gelesen das Minesweaper NP Vollständig sei. Was das heißt wei ich aber leider nicht... 
Vielen Dank! 
|
||||
| 05.03.2012, 19:57 | Dopap | Auf diesen Beitrag antworten » | ||
also, bei allem Wohlwollen. Was erwartest du als Antwort? etwas was du verstehen kannst? Glaube ich nicht. aber warten wir ab... |
||||
| 05.03.2012, 20:18 | Cheftheoretiker | Auf diesen Beitrag antworten » | ||
Wer nicht helfen kann muss ja nicht antworten! 
|
||||
| 07.03.2012, 13:23 | lp-raum | Auf diesen Beitrag antworten » | ||
Ich bin kein Experte, aber die Darstellung in diesem Video h ttp: //w ww.livestream.c om/newintellige nce/video?clipId=pla_c31fb902-cd4e-410e-ba00-c0ae59b3ba0a finde ich ziemlich interessant & gut erklärt (es geht eigentlich primär um einen fehlgeschlagenen Beweisversuch von ). (Bitte Leerzeichen beim Link entfernen.) |
||||
| 07.03.2012, 18:17 | gonnabphd | Auf diesen Beitrag antworten » | ||
Eine nicht-technische Beschreibung des Problems (zugeschnitten auf ein Laienpublikum) gibt es z.B. in einem Vortrag darüber auf der Clay-Mathematics Homepage zu finden: http://www.claymath.org/video/ (runterscrollen zu P vs. NP) |
||||
| 03.02.2015, 16:28 | Finchinator | Auf diesen Beitrag antworten » | ||
P vs NP ist recht einfach zu verstehen: Für jedes Problem gibt es eine oder mehrere Lösungen. In der Informatik nennt man so eine Lösung einen Algorithmus. Beispiel: Du willst ein Buch aus der Bibliothek ausleihen. Lösung 1: Du gehst durch alle Regal-reihen und ziehst jedes Buch heraus bis du das richtige findest. Lösung 2: Du suchst im Verwaltungssystem nach dem Regal in dem dein Buch steht. Offensichtlich ist Lösung 2 besser, weil schneller. Darum geht es bei P vs NP. P bezeichnet eine Gruppe oder Klasse von Problemen (Wie: "Wo ist das Buch?"), welche sich durch schnelle Algorithmen lösen lassen, d.h. durch Algorithmen, deren Größe sich in Abhängigkeit von der Größe des Problems (i.e. wie viele Bücher gibt es?) definitiv berechnen lässt. NP ist eine Klasse von Problemen, deren Lösung sich (bisher) nicht so erfassen lässt. Für ein "NP-Schweres"-Problem kann man nur 'langsame' Algorithmen (wie jedes einzelne Buch aus den Regalen zu nehmen) anwenden. Beschleunigen lässt sich dies nur durch mehr Rechenkapazität (i.e. mehr Computer oder mehr Leute die nach dem selben Buch suchen). NP schließt dabei P ein, d.h. (in einfachen Worten) ist jedes Problem erst mal NP bis bewiesen wird, dass es P ist, es gibt mehr NP-Probleme. NP-Probleme sind beispielsweise die frage nach dem besten Schachzug oder die schnelle Lösung eines Sudokus. Auch Verschlüsselungstechniken basieren auf NP-Problemen. P vs NP stellt jetzt die frache nach dem Verhältnis zwischen diesen Klassen. Entweder ist P definitiv ungleich NP, was bedeutet, dass jemand beweisen muss, dass mindestens EIN NP-Schweres-Problem unmöglich mit einem schnellen Algorithmus lösbar ist (i.e. dieser auch nicht theoretisch entdeck werden KANN) ODER P ist gleich NP. Das ließe sich ebenfalls dadurch beweisen, dass nur ein NP-Schweres-Problem gelöst würde, da diese faktisch alle auf dem selben Grundprinzip basieren und somit die Lösung eines Problems automatisch ALLE lösen würde (funktioniert aber auch genau so mit der UNlösbarkeit). FunFact: Der Vorgang des 'Beweisens' ist selbst ein NP-Schweres-Problem, spätestens hier dreht man sich im Kreis ;-) Der Nachweis von entweder P = NP oder der Ungleichheit von P und NP ist mit 1 Million US-Dollar notiert. Hoffe, ich konnte weiter helfen. (3 Jahre zu spät) |
||||
| Anzeige | ||||
|
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
