thomas
Unregistrierter Gast
| Veröffentlicht am Dienstag, den 30. April, 2002 - 10:19: |
|
Ich weiß das dieser Beitrag schon mal gestellt worden ist....aber scheinbar hat die Überschrift nur "Interesse " hervorgerufen...also wenn jemand mir ( und Lisa ) konstruktiv helfen kann wäre schön...thomas 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. |