Reduzierbarkeit von 2 booleschen Befriedigungsproblemen
-
29-09-2020 - |
Frage
Ich bitte um Hilfe bei diesem Problem.
Es gibt 2 boolesche Befriedigungsprobleme.
problem $ A $ : Bestimmen, ob eine beliebige Formel der Größe $ n $
$ erfüllt $ .
Problem $ B $ : Bestimmen, ob eine beliebige Formel der Größe $ n-1 $ $ erfüllt $ in welcher $ n $ ist eine positive Integer $ \ ge 2 $Beweisen Sie, dass $ A $ lösbar sein kann, wenn $ B $ lösbar ist.
Ich denke, die Lösung würde zeigen, dass $ A $ Turning-reduzierbar auf $ B $ . Es bedeutet, dass ich den Oracle-Algorithmus von $ B $ anzeigen muss, der den Oracle-Algorithmus von $ A $ ableitet.
Wie Sie sehen, ist die beliebige Formel von $ B $ $ n-1 $ , aber Das von $ A $ ist $ n $ . Wie kann ich angenommen werden, dass der Oracle-Algorithmus über $ A $ aus dem Oracle von $ B $ B $ , was Bestimmt die Formel von 1-geringerer Größe als der von $ B $ ?
Lösung
Problem A ist bei Problem B auf die folgende Weise reduzierbar:
- .
- Wählen Sie eine Variable in problemat ein und setzen Sie sie auf 0
- Jetzt haben wir eine Formel der Größe N-1, wenn sie mit B zufriedenstellend ist, dann erfüllen Sie die Zufriedenheit Wählen Sie ansonsten erneut ein Problem ein und setzen Sie die Variable auf 1
- Jetzt haben wir wieder eine Formel der Größe N-1, wenn sie mit B zufriedenstellend ist, dann ermessen Sie die Zufriedenheit, die sonst zurückgegeben werden sollen, um unzufrieden zu werden
Mit anderen Worten: Teilen Sie das Problem A in zwei Probleme B mit einer beliebigen Variablen.Wenn B für 0 und 1 unbefriedigbar sagt, ist es nicht zufriedenstellbar.Wenn es für mindestens einen der beiden befriedigend ist, ist es befriedigt.