Reduktion von DOPPELSAT (DOUBLESAT) auf SAT |
24.05.2013, 14:51 | ilikecola | Auf diesen Beitrag antworten » | ||
Reduktion von DOPPELSAT (DOUBLESAT) auf SAT Hallo, ich habe folgendes Problem: Es ist zu zeigen, dass sich das Problem DOPPELSAT (Boolsche Formel, mit mindestens zwei erfüllenden Belegungen) auf SAT (Boolsche Formel, mit mindestens einer erfüllenden Belegung) polynomiell reduzieren lässt. D.h. DSAT <=p SAT. In der entsprechenden Fachliteratur ist leider nur die umgekehrte Richtung zu finden. Meine Ideen: Eine erste Idee war, die boolsche Formel zu nehmen, und diese mit einem UND mit der negierten Formel (d.h. Umkehrung / Negierung aller Literale) zu verbinden. Bsp.: besitzt exakt 2 erfüllende Belegungen wird zu besitzt bedauerlicherweise keine erfüllende Belegung mehr Hat jemand noch einen anderen Ansatz? Danke für jeden Hinweis! |
||||
24.05.2013, 18:40 | zyko | Auf diesen Beitrag antworten » | ||
RE: Reduktion von DOPPELSAT (DOUBLESAT) auf SAT
Wie bist du denn auf diesen Ausdruck gekommen? Du machst dir das Leben leichter, wenn du in der Formel setzt und die Formel auswertest wirst du feststellen, dass sich ergibt, was sich auch durch Erstellen einer Wahrheitstabelle ergibt. |
||||
09.02.2014, 11:46 | kiste | Auf diesen Beitrag antworten » | ||
Falls nur zu zeigen ist, dass es reduzierbar ist: Dies ist trivial. Benutze einfach eine "wichtige" Eigenschaft von SAT. Die Konstruktion einer Reduktion ist ungleich schwieriger. edit: Oo, keine Ahnung wie ich auf den Thread gekommen bin. Sehe erst jetzt, dass der schon alt ist |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|