Warum sind NP-Probleme genannt auf diese Weise (und NP-hart und NP-vollständig)?

Question

Wirklich .. Ich bin mit dem letzten Test für die Graduierung an diesem Dienstag, und das ist eines der Dinge, die ich einfach nie verstehen konnte. Mir ist klar, dass eine Lösung für NP-Problem in Polynomialzeit verfied werden. Aber was bedeutet Determinismus hat mit diesem?
zu tun Und wenn Sie mich erklären konnte, wo NP-vollständig und NP-schwer, ihre Namen bekam, das wäre toll (ich bin mir ziemlich sicher, erhalte ich die Bedeutung von ihnen, ich sehe einfach nicht, was ihre Namen mit dem, was zu tun haben, sie sind).
Sorry, wenn das ist trivial, ich kann einfach nicht scheinen, um es zu bekommen (-:
Dank alle!

Answer 1

P

Klasse aller Probleme, die durch eine gelöst werden kann deterministisch Turing-Maschine in Polynomzeit.

NP

Klasse aller Probleme, die durch eine nicht-deterministisch Turing-Maschine in polynomialer Zeit gelöst werden können (sie auch überprüft werden können durch eine deterministischen Turing-Maschine in polynomialer Zeit. )

NP-Hard

Eine Klasse von Problemen, die „mindestens so hart wie die schwierigsten Probleme in NP“ sind. Formal ist ein Problem in NP-Hard iff es ein NP-vollständiges Problem ist, dass Polynomzeit Turing-reduzierbar ist; (Auch: iff es in polynomialer Zeit durch ein Orakel Maschine mit einem Orakel für das Problem gelöst werden kann). Es ist ziemlich offensichtlich, wo der Name herkommt.

NPC

Die Klasse von Problemen, die sowohl NP sind sowie NP-Hard. In Bezug auf die Namensgebung, auch wikipedia nicht sicher, warum es benannt ist, wie es ist.

Answer 2

Beginnen wir mit „nicht deterministisch“. Eine deterministische Maschine kann zu einer Zeit in einem Zustand sein. Wir können tatsächlich sie machen. Eine nichtdeterministische Maschine ist ein theoretisches Konstrukt, das in mehr als ein Zustand zu einem Zeitpunkt sein kann. (Es gibt Ähnlichkeiten mit Quantencomputing hier, aber für unsere Zwecke hier sind sie irreführend. Sie ignorieren.)

Wenn wir ein Problem mit einer deterministischen Maschine lösen wollen, beginnen wir es auf, und es geht durch eine Reihe von Schritten, um zu versuchen, ein Problem zu finden. Wenn wir eine nichtdeterministische Maschine-Modell, kann es durch alle möglichen Reihen von Schritten zur gleichen Zeit gehen.

Die Problematik werden wir besorgt sein mit sind Entscheidungsprobleme: Da eine Problemstellung, entweder gibt es eine Lösung oder nicht. Finden Sie eine Lösung oder berichten, dass es keine gibt. Zum Beispiel annimmt, dass Sie eine Reihe von logischen Aussagen haben: A oder nicht-B, B oder C oder D, nicht-D oder A oder B, .... eine beliebige Menge gegeben, können Sie Wahrheitswerte für alle Variablen finden so dass alle die Aussagen wahr sind?

Nun wollen wir betrachten die P. wir die Größe eines Problems von n darstellen Angenommen. Die Größe könnte die Zahl der Städte in einem traveling salesman Problem sein, die Anzahl der logischen Aussagen in dem Problem oben, was auch immer. Bei einem bestimmten n, wird das Problem eine bestimmte Menge an Ressourcen erfordern auf einem bestimmten System zu lösen. Wenn wir nun die Ressourcen oder Rechenfähigkeit verdoppeln, was passiert mit der Größe des Problems wir lösen können? Wenn das Problem von Polynom Komplexität ist, die in P bedeutet, geht die Größe durch einen bestimmten Anteil auf. Es könnte verdoppeln oder um 40% steigen, oder 10%. Im Gegensatz dazu, wenn es von exponentieller Komplexität ist, geht die Größe durch eine bestimmte Zahl. Wir denken im Allgemeinen von P Probleme als lösbar und exponentielle Probleme als unlösbares wie die Probleme groß werden, aber das ist eine Vereinfachung ist. Von einer informellen Sicht ist Polynom Komplexität Figur Dinge über das Problem der Lage der Reihe nach, während exponentiell an allen möglichen Kombinationen zu betrachten ist, mit.

Angenommen, wir das Problem in polynomieller Zeit auf einer deterministische Maschine lösen können. Das Problem ist in P. Angenommen, wir es in polynomialer Zeit auf einer nichtdeterministische Maschine lösen können, was das gleiche wie in der Lage ist, eine vorgeschlagene Lösung in polynomialer Zeit auf einer deterministische Maschine zu überprüfen. Dann ist das Problem in NP. Der Trick dabei ist, dass wir nicht wahr nondeterministic Maschinen machen können, so dass die Tatsache, dass ein Problem in NP ist, bedeutet nicht, es ist praktisch zu lösen.

Nun zu NP-vollständig. Alle Probleme in P sind in NP. Für Probleme A und B in NP, könnten wir in der Lage sein zu sagen, dass, wenn A in P ist, so ist B. Dies wird durch einen Weg finden, neu zu formulieren B als eine Art von Problem erledigt ist. Ein NP-vollständiges Problem ist eine solche, dass, wenn es in P ist, jedes Problem in NP in P. ist, wie Sie sich vorstellen kann, einen Weg zu finden, jedes mögliche Problem neu zu formulieren als ein bestimmte nicht leicht war, und ich werde nur sagen, dass das Problem mit dem logischen Aussagen über (das Erfüllbarkeitsproblem) war der erste erwies sich als NP-vollständig. Danach war es einfacher, da es nur notwendig, um zu beweisen, war, dass, wenn das Problem C in P war, so war Erfüllbarkeit.

Es wird allgemein angenommen, dass es Probleme gibt, die in NP sind aber nicht P, und ein Beweis wurde vor kurzem veröffentlicht (die gültig oder auch nicht ausfallen sein). In diesem Fall NP-vollständige Programme sind die härtesten Arten von Problemen in NP.

Es gibt Probleme, die in dieser Form nicht passen. Das reisende Salesman Problem, wie es normalerweise gestellt, ist die günstigste Route verbindet alle Städte zu finden. Das ist kein Entscheidungsproblem, und wir können jede vorgeschlagene Lösung nicht direkt überprüfen. Wir können es als Entscheidungsproblem neu formulieren: Da eine kostengünstige C gibt es eine Route, die billiger als C ist? Dieses Problem ist NP-vollständig, und mit einer wenig Arbeit können wir die ursprüngliche TSP über so leicht wie das modifiziert, NP-vollständig, Form zu lösen. Daher ist die TSP NP-hart, da es‚S mindestens so hart wie ein NP-vollständiges Problem.

Answer 3

NP NP genannt (nichtdeterministischen Polynomialzeit), weil ein NP-Problem in Polynomialzeit durch eine nichtdeterministische Turingmaschine gelöst werden.

Answer 4

Lassen Sie uns beginnen mit NP: in NP, N für „nicht deterministisch“ und P für „Polynom Zeit“. Es ist die Klasse von Problemen, die in polynomieller Zeit gelöst werden können, wenn Sie eine nicht deterministische Turing-Maschine, die bei jedem Zyklus verzweigen zu erkunden Möglichkeiten parallel (die „Verify die Lösung“ hat alternative Definition populär vor kurzem worden, aber es macht nicht klar, was "N" bezeichnet). Die nichtdeterministische Maschine kann mit einer unendlichen Anzahl von Prozessoren, und der Fähigkeit, fork() bei jedem Befehl zu einem parallelen Computer verglichen werden.

Zu sagen, dass ein Problem Q "NP-hard" bedeutet, dass jedes Problem in NP zu Problem Q reduziert werden (in polynomialer Zeit). Da die Beziehung zwischen Problemen „kann reduziert werden“ ist eine Ordnungsrelation, kann man sich vorstellen „NP-hard“ im Sinne von „mindestens so hart wie alle NP-Problemen“.

Ein "NP-complete" Problem ist nur eines der Probleme in NP, die NP-hart ist. Ich denke, dass Klasse von Problemen einen Namen brauchte, aber ich bin nicht sicher, wie die Wahl des Wortes „vollständig“ zu erklären.

Answer 5

Aber was bedeutet Determinismus hat damit zu tun?

Wikipedia :

NP ist die Menge aller Entscheidungsprobleme, für die die ‚Ja'-Antworten haben effizient nachprüfbare Beweise für die Tatsache, dass die Antwort ist in der Tat‚Ja‘. Genauer gesagt, haben diese Beweise nachprüfbar in Polynomialzeit sein von einer deterministischen Turing-Maschine

Nicht sicher über die Geschichte der allerdings Namen. EDIT: Ich habe Vermutungen though. Was folgt, ist Spekulation, aber ich glaube nicht, dass es unvernünftig ist.

NP-Hard ist ein Problem, die mindestens so hart wie die schwierigsten Probleme in NP ist. Daher könnte man sagen, dass das Problem in Frage NP Härte würde., Also NP-Hard.

Wenn irgendein einzelnes Problem in NP-vollständig können schnell gelöst werden, dann jedes Problem in NP können auch schnell gelöst werden. Daher könnte der komplette Satz von NP-Probleme gelöst werden.

EDIT2 : Wikipedias Complete (Komplexität) Artikel zeigt:

ein Rechenproblem ist komplett für eine Komplexitätsklasse, wenn es in einem formalen Sinne, einer der „härtesten“ oder „ausdruck“ Probleme in der Komplexitätsklasse