    
lisa
Unregistrierter Gast
| | Veröffentlicht am Samstag, den 27. April, 2002 - 08:28: | 
|
SAT ist das Problem , zu entscheiden , ob eine als Eingabe vorliegende Boolsche Formel erfüllbar ist oder nicht.
a)
Zeigen Sie, dass das Problem SAT eingschränkt auf
DNF-Formeln in P liegt.
b)
Zeigen Sie , das das Problem SAT, eingeschränkt auf CNF-Formeln mit n<=log m Variablen in Pliegt.
c) zeigen Sie dass das Problem SAT eingeschränkt
auf CNF-Formeln in denen jede Variable (negiert)oder nicht negiert höchstens zweimal vormkommt in P liegt. |
