Ich versuche (intuitiv) die beiden Begriffe "Entscheidbarkeit" und "Überprüfbarkeit" zu verstehen.
Ich habe die verschiedenen Texte, die ich in die Hände bekommen kann, angemessen durchsucht und durchgesehen. Ihr intuitives Verständnis scheint mir jedoch zu entgehen, besonders für das zweite.
Von den vielen gefundenen Definitionen hat mir die folgende auf dieser Seite klar die Entscheidbarkeit erklärt.
Eine Sprache wird als entscheidbar bezeichnet, wenn es eine Methode gibt - eine Methode überhaupt -, um zu bestimmen, ob ein bestimmtes Wort zu dieser Sprache gehört oder nicht.
Ich finde jedoch keine parallele Definition für die Überprüfbarkeit.
Im Buch Theory of Computation von Sipser finden wir:
P = die Klasse der Sprachen, für die eine Mitgliedschaft schnell entschieden werden kann.
NP = die Klasse von Sprachen, für die die Mitgliedschaft schnell überprüft werden kann.
Vor diesem Hintergrund möchte ich die Überprüfbarkeit verstehen.
Bitte geben Sie so viele Beispiele wie möglich an. In einem Moment versuche ich, die Bedeutung zu verstehen. Im nächsten Moment bin ich wieder verwirrt.
Antworten:
Der Schlüssel zum Verständnis hier ist, dass P und NP Klassen von Entscheidungsproblemen sind. Das bedeutet, dass alle Ja / Nein-Antworten haben.
Wenn wir also sagen, dass ein Problem wie 3-SAT NP-vollständig ist, bedeutet dies, dass bei einer Instanz von 3-SAT (auch bekannt als ein Wort, das möglicherweise in der Sprache enthalten ist) kein effizienter Weg bekannt ist, um zu testen, ob das Wort ist oder nicht in der Sprache.
Zu sagen, dass etwas in NP ist, bedeutet, dass es für jede Zeichenfolge in der Sprache eine Art "Beweis" gibt, der in der Länge der Eingabe polynomisch ist.
In 3-SAT fragen wir beispielsweise, ob es eine Zuordnung von Richtig / Falsch zu einer Reihe von Variablen in einer booleschen Formel gibt, sodass sich herausstellt, dass die Formel wahr ist. Das Wort, das wir testen, ist die Boolesche Formel. Es ist nicht bekannt, ob es eine einzige Lösung gibt, die die gesamte Formel wahr macht. Wenn wir jedoch eine Reihe von Wahr / Falsch-Werten für die Variablen haben, ist es sehr einfach zu überprüfen (in Polynomzeit), ob die Formel dadurch als wahr ausgewertet wird.
Der entscheidende Punkt hierbei ist, dass das Wort, das wir testen, NICHT die wahren / falschen Werte für jede Variable sind. Das Wort, das wir testen, ist die Formel, die die Variablen enthält, und die Sprache ist die Menge aller booleschen Formeln, die als wahr ausgewertet werden.
Wir wissen nicht, wie wir effizient testen können, ob das Wort (die Formel) in der Sprache vorliegt (kann als wahr bewertet werden), aber wenn wir eine Reihe von wahr / falsch-Zuweisungen erhalten, können wir überprüfen, ob es als wahr bewertet wird, dh es ist ein "Beweis" "dass das Wort (Formel) in der Sprache ist. Somit liegt das Problem in NP, aber es ist nicht bekannt, dass es in P liegt.
NP ist eigentlich die Klasse nicht deterministischer polynomlösbarer Entscheidungsprobleme. Dies liegt daran, dass wir in einer nicht deterministischen Turingmaschine "Entscheidungspunkte" haben, an denen wir eine von mehreren Aktionen ausführen können, und unser Polynomzertifizierer sagt im Grunde nur, welche Entscheidung an jedem Entscheidungspunkt zu treffen ist.
quelle
Angenommen, Sie geben mir ein Problem und haben mich um eine Lösung gebeten. Nehmen wir also an, Sie können nur die Polynommenge meines Beweises überprüfen (dh Sie können ein effizientes Computerprogramm für meinen Beweis ausführen), wenn ich Ihnen meinen Beweis für die Lösung sende Sie müssen Ihr Programm ausführen und entscheiden, was das Programm ausgibt.
Beispiel: Angenommen, Sie fragen mich, ob ein Diagramm dreifarbig ist. Dann muss ich eine dreifarbige Darstellung des Diagramms senden. Anschließend prüfen Sie, ob alle benachbarten Scheitelpunkte unterschiedliche Farben haben. Die Farbgebung ist zulässig und das Programm endet mit "akzeptieren" (andernfalls wird der Beweis nicht akzeptiert und wir beenden mit "ablehnen").
Das wird aufgerufen, um "schnell" zu überprüfen.
Wenn Sie ein "effizientes" "Computerprogramm" (oder einfach: Polynomalgorithmus) erstellen können, das besagt, ob eine Eingabe (eine Zeichenfolge mit der Länge n) in der Sprache vorliegt (oder wenn die Programmausgabe 1 "akzeptieren"), ist dies das Richtige meine mit Komplexitätsklasse P.
Beispiel: Angenommen, ich gebe Ihnen eine Liste von Zeichenfolgen (sagen wir Telefonbuch) und frage Sie nach einem Namen, den Sie sagen müssen, ob er im Buch enthalten ist oder nicht. Eine Lösung besteht darin, alle Namen zu werfen und jeden Namen mit dem angegebenen Namen zu vergleichen, der besagt, dass Sie ihn in linearer Zeit lösen können.
Ein anderes Beispiel ist: gegeben ein Diagramm G = (V, E) und eine Kante e = (u, v) und Sie möchten sagen, ob sich die Kante im Diagramm befindet.
quelle