NL: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „NL ist die nichtdeterministische Variante von NL. '''TODO''' Kategorie:TODO“) |
Css (Diskussion | Beiträge) |
||
| Zeile 1: | Zeile 1: | ||
NL ist die nichtdeterministische Variante von NL. | 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. | ||
| + | |||
[[Kategorie:TODO]] | [[Kategorie:TODO]] | ||
Version vom 29. August 2018, 20:25 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.
