Einfache Frage zu Entscheidungsproblemen

8

(Ich bin mitten in meinem ersten theoretischen CSS-Kurs, also entschuldige ich mich im Voraus für die wahrscheinlich dumme Frage.)

Wir sagen also, dass eine Sprache L in P ist, was bedeutet, dass eine Turing-Maschine konstruiert werden kann, die eine 1 ausgibt, wenn x in L ist und andernfalls 0; Außerdem läuft die Maschine in Polynomzeit. Ich verstehe das.

Aber viele Leute sagen, dass es bestimmte Probleme in P gibt, die mir nicht als Entscheidungsprobleme erscheinen; Zum Beispiel das Maximieren einer Funktion, die linearen Einschränkungen unterliegt. Was bedeutet es, dass "lineare Programmierung" in P ist? Sicherlich ist "den Maximalwert finden" kein Entscheidungsproblem?

cc.complexity-theory Xodarap
quelle

Antworten:

16

Sie haben Recht: Formal enthält P nur Entscheidungsprobleme. Viele Entscheidungsprobleme haben jedoch entsprechende Optimierungsprobleme: Ermitteln Sie die Größe der größten Übereinstimmung in einem Diagramm, ermitteln Sie die Länge des kürzesten Pfades von s nach t in einem Diagramm usw.

Oft können diese auf Entscheidungsprobleme reduziert werden, indem stattdessen gefragt wird: "Hat der Graph eine Übereinstimmung mit mehr als k Kanten?" oder "Gibt es einen s-> t-Pfad mit einer Länge von weniger als k?"

Wenn Sie das Optimierungsproblem lösen können, können Sie natürlich das Entscheidungsproblem lösen. Das Gegenteil ist auch oft der Fall, bis hin zu logarithmischen Faktoren. Wenn Sie beispielsweise die Größe der größten Übereinstimmung in einem Diagramm wissen möchten, können Sie Ihren Algorithmus wiederholt aufrufen, um das Entscheidungsproblem "Hat das Diagramm eine Übereinstimmung mit mehr als k Kanten?" und binäre Suche nach dem Wert "k". Auf diese Weise benötigen Sie höchstens log (m) -Aufrufe, wobei m die Anzahl der Kanten ist. Für die meisten Probleme gibt es eine analoge Reduzierung.

Aaron Roth
quelle
Um der Antwort von Aaron zu folgen, kann die lineare Programmierung als Entscheidungsproblem formuliert werden, indem eine Grenze k angegeben wird, an der Sie interessiert sind. Dies ist ein häufiger Trick. Gibt es zum Beispiel eine Zuordnung von Werten zu Variablen der Zielfunktion, so dass Sie alle linearen Bedingungen erfüllen UND die Zielfunktion einen Wert größer oder gleich (bzw. kleiner als oder gleich) k hat? Sie können dies beispielsweise in Polynomzeit entscheiden, indem Sie die Zielfunktion maximieren / minimieren.
Daniel Apon
Also im Wesentlichen, wenn Sie wissen, "gibt es eine Lösung für X?" Ist in P dann normalerweise (aber nicht immer) das Problem " Was ist die Lösung für X?" wird in Polynomzeit lösbar sein?
Xodarap
3
Xodarap: das stimmt. Normalerweise können Sie das Suchproblem schnell lösen, aber nicht immer. Als berühmtes Gegenbeispiel: Nach Nashs Theorem hat jedes Matrixspiel ein gemischtes Nash-Gleichgewicht, daher ist die Lösung des Entscheidungsproblems "Hat dieses Spiel ein Nash-Gleichgewicht" trivial - die Antwort lautet Ja. Es wird jedoch angenommen, dass es schwierig ist, in einem generischen Spiel tatsächlich ein Nash-Gleichgewicht zu finden.
Aaron Roth
Ein weiteres Beispiel hierfür ist der Satz von Radon. Wenn d + 2 Punkte in R ^ d gegeben sind, gibt es eine Aufteilung der Punkte in zwei Mengen, so dass sich die beiden konvexen Hüllen schneiden. Eine Kandidatenpartition ist leicht zu überprüfen, aber schwer zu finden.
Suresh Venkat
11

Formal wird die Klasse von Funktionen , die in Polynomzeit berechnet werden kann, FP genannt . Die Leute sagen oft "P" anstelle von "FP", da die Unterscheidung nur syntaktisch ist und keine wirkliche Verwirrung entsteht.

Noam
quelle
8

Eine sehr ähnliche Frage wurde bereits im Thema " FNP-Komplexitätsklasse " gestellt. Dort stellte der Fragesteller im Wesentlichen den Unterschied zwischen den NP- und FNP-Komplexitätsklassen. Sie fragen nach dem Unterschied zwischen den Komplexitätsklassen P und FP. Kurz gesagt, P und NP sind Entscheidungsklassen, während die "F" -Versionen (FP und FNP) Funktionsklassen sind. Weitere Informationen finden Sie im oben genannten Thema.

MS Dousti
quelle
7

Probleme, die eine Lösung erfordern, können in Entscheidungsprobleme umgewandelt werden, wenn es eine Möglichkeit gibt, zu messen, wie gut eine Lösung ist. Die Entscheidungsversion gibt an, dass jede Lösung besser als ein Schwellenwert sein muss. Zum Beispiel wird die Entscheidungsversion von LINEAR PROGRAMMING erhalten, indem gefragt wird, ob das lineare Programm durchführbar ist.

András Salamon
quelle
Ah, ich bin mir dessen eigentlich nicht bewusst - ist die Entscheidung, ob es eine praktikable Lösung gibt, häufiger als die Entscheidung, ob es eine realisierbare Lösung mit einem bestimmten Wert gibt?
Daniel Apon
1
C.X.≥B.X.C.B.- -C.X.≤- -B.C.X.≥B.