• Das Problem
• Die Lösung
• Zusammenfassung

Wenn Sie Zeit in oder um die Programmiergemeinschaft verbringen, hören Sie wahrscheinlich den Begriff“ P gegen NP “ ziemlich häufig. Leider haben selbst viele mit formaler Informatikausbildung ein schwaches Verständnis des Konzepts.

Also hier ist eine einfache und prägnante Erklärung:

Das Problem

P vs. NP Das Problem P vs. NP fragt, ob jedes Problem, dessen Lösung von einem Computer schnell verifiziert werden kann, auch schnell von einem Computer gelöst werden kann., (Wikipedia)

Also lasst uns herausfinden, was wir mit P und NP meinen.

P Probleme werden leicht von Computern gelöst, und NP Probleme sind nicht leicht lösbar, aber wenn Sie eine mögliche Lösung präsentieren, ist es leicht zu überprüfen, ob es richtig ist oder nicht.

Wie Sie dem obigen Diagramm entnehmen können, sind alle P-Probleme NP-Probleme. Das heißt, wenn es für den Computer einfach zu lösen ist, ist es einfach, die Lösung zu überprüfen. Das P vs NP-Problem fragt also nur, ob diese beiden Problemtypen gleich sind oder ob sie unterschiedlich sind, dh dass es einige Probleme gibt, die leicht verifiziert, aber nicht leicht zu lösen sind.,

Es scheint derzeit, dass P ≠ NP, was bedeutet, dass wir viele Beispiele für Probleme haben, auf die wir schnell mögliche Antworten überprüfen können, die wir jedoch nicht schnell lösen können. Schauen wir uns ein paar Beispiele an:

• Ein reisender Verkäufer möchte 100 verschiedene Städte besuchen, indem er fährt, seine Reise zu Hause beginnt und beendet. Er hat einen begrenzten Vorrat an Benzin, so dass er nur insgesamt 10.000 Kilometer fahren kann. Er möchte wissen, ob er alle Städte besuchen kann, ohne dass ihm das Benzin ausgeht., (aus Wikipedia)
• Ein Bauer möchte 100 Wassermelonen verschiedener Massen auf den Markt bringen. Sie muss die Wassermelonen in Kisten packen. Jede Box kann nur 20 Kilogramm halten, ohne zu brechen. Der Bauer muss wissen, ob 10 Kisten ausreichen, um alle 100 Wassermelonen auf den Markt zu bringen. (aus Wikipedia)

Alle diese Probleme haben ein gemeinsames Merkmal, das der Schlüssel zum Verständnis der Intrigen von P gegen NP ist: Um sie zu lösen, müssen Sie alle Kombinationen ausprobieren.

Die Lösung

Deshalb ist die Antwort auf die P vs., Dieses Problem ist für Menschen so interessant. Wenn jemand zeigen könnte, dass P gleich NP ist, würde dies schwierige reale Probleme für Computer trivial machen.

Zusammenfassung

1. P vs. NP befasst sich mit der Lücke zwischen Computern, die in der Lage sind, Probleme schnell zu lösen, anstatt nur vorgeschlagene Lösungen auf Richtigkeit zu testen.
2. Als solches ist das P vs. NP-Problem die Suche nach einer Möglichkeit, Probleme zu lösen, die das Ausprobieren von Millionen, Milliarden oder Billionen von Kombinationen erfordern, ohne tatsächlich jede ausprobieren zu müssen.,
3. Die Lösung dieses Problems hätte tiefgreifende Auswirkungen auf das Rechnen und damit auf unsere Gesellschaft.

Feb 7, 2017 — Added-Wikipedia Zuschreibungen.
2. März 2014-Bereinigt einige der Erklärung, um Verwirrung zu vermeiden.

Hinweise