Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

SAT und CNF, DNF

ZahlReich - Mathematik Hausaufgabenhilfe » ---- Archiv: Universitäts-Niveau » Mathematik für Informatiker » SAT und CNF, DNF « Zurück Vor »

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

thomas
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Dienstag, den 30. April, 2002 - 10:19:   Beitrag drucken

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.

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page