Laufzeit von constraint satisfaction problems (bspw. Map coloring)
-
In meinem Skript steht folgendes:
CSPs die diskret sind und finite Domänen haben sind die einfachen CSPs (bspw. map coloring).
Boolean CSPs sind diskrete deren finite Domäne nur true/false ist (bspw. 3SAT), 3SAT ist NP-complete.
und nun kommt's:
Diskrete mit infiniten Domänen benötigen irgendeine Art von constraint language (bspw. Var1 + 5 < Var2), solange diese Constraints aber LINEAR sind kann man mit linearer Programmierung eine Lösung in POLYNOMIELLER Zeit finden.
Wie zum Kuckuck? Wieso kann ich bei infiniter Domäne schneller eine Lösung finden als bei finiter Domäne?? Das kann doch nicht sein, oder? Oder sind 3SAT-Constraints nicht linear? Doch, oder?!
MfG SideWinder
-
Wenn man mit reellen Zahlen rechnen darf, dann ist lineare Optimierung polynomiell. Diskret oder nicht diskret ... dann: konvex oder nicht konvex, das ist hier die Frage.
-
Welche Vereinfachung haben die, das es dann so schnell läuft?
MfG SideWinder
-
SideWinder schrieb:
Welche Vereinfachung haben die, das es dann so schnell läuft?
Du kannst Einheiten unendlich/beliebig teilen.
-
knivil schrieb:
Wenn man mit reellen Zahlen rechnen darf, dann ist lineare Optimierung polynomiell.
Wenn die Eingabe rational ist gehts auch polynomiell. -> Ellipsoidmethode
-
SideWinder schrieb:
Welche Vereinfachung haben die, das es dann so schnell läuft?
Zum Beispiel bei der linearen Optimierung weißt Du, dass die Lösungsmenge ein Polyeder ist und die optimalen Punkte auf dem Rand des Polyeders liegen. Damit kannst Du das Polyeder mehr oder weniger gezielt absuchen. Wenn Du jetzt aber ein diskretes Problem nimmst, beispielsweise lineare Programme mit ganzzahligen Variablen, dann schneidest Du im Prinzip das Lösungspolyeder des linearen Programms mit einem Gitter. Und diese Struktur ist bedeutend schwieriger abzusuchen, weil eben nicht unbedingt gute Gitterpunkte auf dem Rand des Polyeders liegen, sondern halt irgendwo im Inneren.
Man kann 3SAT schon als lineares Programm formulieren, braucht dafür aber ganzzahlige Variablen. Genau das macht das Problem aber eben sehr schwierig.
-
Danke für eure Informationen.
Woher wisst ihr darüber (so gut) Bescheid?
MfG SideWinder