NL: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) |
Css (Diskussion | Beiträge) (→Beispiel) |
||
| Zeile 5: | Zeile 5: | ||
Das 2SAT-Problem ist in NL: | 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. | + | 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) $ | ||
[[Kategorie:TODO]] | [[Kategorie:TODO]] | ||
Version vom 29. August 2018, 20:27 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) $
