N versus NP...for dummies

[reBourne]

Hi,

also ich würde mal gerne das N=NP gerne kurz und einfach verständlich erklärkt bekommen,weil ich aus dem Artikel in Wikipedia nicht schlau werde...oder aus anderen Artikeln wo man seitenlang Fachwörter wie Komplexitätsklasse oder nichtdeterminischtische Polynomialzeit...etc an den Kopf geschmissen bekommt!?
kennt sich einer mit dem Thema aus?
Ich bin mir sicher man kann aus auch mit Bienchen und Blümchen erklären
also wer weiss rat?

 

[kabel2]

das heisst P=NP

für probleme in der "Klasse" P gibt es Algorithmen, die "relativ effizient" (polynomial) eine lösung berechnen.

für probleme der "Klasse" NP gilt etwas komisches: mal angenommen, du hat einen lösungskandidat. dann kannst du "relativ effizient" (s.o.) feststellen, ob es tatsächlich eine lösung ist. das ist nicht das problem. das problem ist, dass es exponentiell viele ( "gaaanz viele" ) lösungskandidaten gibt.

was das heisst, erfährst du, wenn du z.b. den term (2^n)/(n^2) für einige n betrachtest.

zum konkreten beispiel: sagt dir "aussagenlogik" was?

 

[reBourne]

zur Klasse NP:
Ist das Traveling Salesman ein Problem zu dieser Klasse?
man hat zear viele Kandidaten,aber es gibt nur 1 kürzesten weg ,oder?

und:

Welche Auswirkungen hat man denn wenn P=NP oder P ungleich NP ist?

 

[kabel2]

beim TSP ist die fragestellung, ob es eine rundreise gibt, die weniger als k längeneinheiten lang ist.

wenn man ein NP-vollständiges problem gelöst hat, hat man alle NP-vollständigen gelöst. man kann nämlich "relativ effizient" die anderen NP-vollst. problem in das gelöste konvertieren. wenn also P=NP gilt, kannst du alle NP-vollst. probleme "relativ effizient" lösen.

zu wikipedia: naja der erste absatz ist schon harter tobak, aber danach ists doch relativ verständlich.

 

[reBourne]

Danke für die erleuchtenden Antworten