Reduktion von DOPPELSAT (DOUBLESAT) auf SAT

24.05.2013, 14:51

ilikecola

Reduktion von DOPPELSAT (DOUBLESAT) auf SAT

Meine Frage:
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.:
$\begin{eqnarray*} \left(a\wedge b\wedge c\right) \vee \left(a\wedge b\wedge \overline{c}\right) \end{eqnarray*}$ besitzt exakt 2 erfüllende Belegungen
wird zu
$\begin{eqnarray*} \left(\left(a\wedge b\wedge c\right) \vee \left(a\wedge b\wedge \overline{c}\right)\right) \wedge \left(\left(\overline{a}\wedge \overline{b}\wedge \overline{c}\right) \vee \left(\overline{a}\wedge \overline{b}\wedge c\right)\right) \end{eqnarray*}$ 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

Zitat:

Bsp.:
$\begin{eqnarray*} \left(a\wedge b\wedge c\right) \vee \left(a\wedge b\wedge \overline{c}\right) \end{eqnarray*}$ besitzt exakt 2 erfüllende Belegungen
wird zu
$\begin{eqnarray*} \left(\left(a\wedge b\wedge c\right) \vee \left(a\wedge b\wedge \overline{c}\right)\right) \wedge \left(\left(\overline{a}\wedge \overline{b}\wedge \overline{c}\right) \vee \left(\overline{a}\wedge \overline{b}\wedge c\right)\right) \end{eqnarray*}$ besitzt bedauerlicherweise keine erfüllende Belegung mehr

Wie bist du denn auf diesen Ausdruck gekommen?

$\begin{eqnarray*} \left(a\wedge b\wedge c\right) \vee \left(a\wedge b\wedge \overline{c}\right) \end{eqnarray*}$
Du machst dir das Leben leichter, wenn du in der Formel
$\begin{eqnarray*} d=a\wedge b \end{eqnarray*}$
setzt und die Formel auswertest
$\begin{eqnarray*} \left(d\wedge c\right) \vee \left(d\wedge \overline{c}\right)=<br /> \left(d\wedge d\right) \vee \left(d\wedge c\right)... \end{eqnarray*}$
wirst du feststellen, dass sich
$\begin{eqnarray*} \left(a\wedge b\wedge c\right) \vee \left(a\wedge b\wedge \overline{c}\right)=a\wedge b \end{eqnarray*}$
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 Big Laugh

Neue Frage »

Antworten »

Reduktion von DOPPELSAT (DOUBLESAT) auf SAT

Verwandte Themen