Was sind NP-Probleme?

Question

las ich den Artikel auf Wikipedia, kann aber nicht verstehen, was genau sind NP-Probleme. Kann mir jemand von ihnen erzählen und auch, was Beziehung von ihnen mit P Problemen?

Answer 1

NP-Probleme sind Probleme, dass eine vorgeschlagene Lösung gegeben, können Sie die Lösung in einem Polynom Zeit überprüfen können. Zum Beispiel, wenn Sie eine Liste der Universitätskurse und Notwendigkeit, einen Zeitplan zu erstellen, so dass Kurse nicht in Konflikt, wäre es eine wirklich schwierige Aufgabe (Komplexität weise) sein. Allerdings gegeben ein vorgeschlagene Zeitplan, können Sie einfach seine Richtigkeit überprüfen.

Ein weiteres wichtiges Beispiel aus dem Bereich der Verschlüsselung: Da eine Zahl, die das Ergebnis zwei sehr große Primzahlen zu multiplizieren, ist es sehr schwierig, diese Primzahlen nur basierend auf dem Ergebnis zu finden. Allerdings gegeben zwei Zahlen, es ist sehr einfach, die Lösung zu überprüfen (multiplizieren sie, zu vergleichen).

Ich habe absichtlich Beispiele gewählt, die in NP sind und nicht in P (d Problem, das schwer sind, um die Lösung zu finden), so dass Sie den Unterschied verstehen. Alle Probleme, die leicht zu lösen sind, sind auch leicht zu überprüfen - nur lösen und vergleichen. Das heißt, P eine Teilmenge von NP ist.

Answer 2

Nicht wirklich eine Antwort, weil Piccolos Link nützlicher ist, aber ein HP-Forscher Ansprüche erwiesen hat P! = NP, hier ist das Papier.

www.hpl.hp.com/personal/Vinay_Deolalikar/Papers /pnp12pt.pdf

Es wurde noch nicht akzeptiert, aber ich wünsche ihm viel Glück für die 1 M $.