NL: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) (→Beispiel) |
Css (Diskussion | Beiträge) (→Beispiel) |
||
| Zeile 8: | Zeile 8: | ||
$ (x_1\vee\neg x_2) \wedge (\neg x_2 \vee x_3) \wedge (x_3 \vee x_4) $ | $ (x_1\vee\neg x_2) \wedge (\neg x_2 \vee x_3) \wedge (x_3 \vee x_4) $ | ||
| + | |||
| + | Die frage ist nun, ob man, gegeben einen 2SAT-Ausdruck, eine Belegung finden kann, die diesen Susdruck wahr macht. | ||
[[Kategorie:TODO]] | [[Kategorie:TODO]] | ||
Version vom 29. August 2018, 20:29 Uhr
NL ist die nichtdeterministische Variante von NL.
Beispiel
Das 2SAT-Problem ist in NL:
Gegeben ist eine logische Formel die sich aus boole'schen Variablen $x_i$ zusammensetzt, die potentiell von einem Negationszeichen $\neg x_i$ negiert wird. Immer zwei dieser Variablen oder negierten Variablen werden mit einem oder-Zeichen $\vee$ verbunden. Diese Disjunktionen werden dann wiederum durch und-Zeichen $\wedge$ verknüpft. Beispiel:
$ (x_1\vee\neg x_2) \wedge (\neg x_2 \vee x_3) \wedge (x_3 \vee x_4) $
Die frage ist nun, ob man, gegeben einen 2SAT-Ausdruck, eine Belegung finden kann, die diesen Susdruck wahr macht.
