Tut 4

Question 1

Beispiel für ein 𝑁𝑃-vollständiges Problem

Answer 1

Beispiele für 𝑁𝑃-vollständige Probleme (nichtdeterministisch polynomiell lösbar):

• 𝑆𝐴𝑇 (Gibt es eine erfüllende Belegung für eine Formel?)
• 𝐶𝐿𝐼𝑄𝑈𝐸 (Gibt es einen vollständig verbundenen Teilgraph der Größe 𝑘?)

Question 2

Komplexität

Answer 2

• obere Schranken: O( )
• untere Schranken Ω( )
• Zeitkomplexität: max {Berechnung kürzesten Konfigurationsfolge}
• Platzkomplexität: max {# der durch Schreiben veränderten Zellen des Bandes in der kürzesten Konfigurationsfolge}

Question 3

DNF

Answer 3

• Disjunktion von Konjunktionstermen
• Man sucht also nur die erste Klausel in der keine Variable sowohl negiert als auch nicht negiert auftaucht. Diese Klausel kann man erfüllen und damit auch die ganze Formel

Question 4

KNF

Answer 4

• Konjunktion von Disjunktionstermen
• Umwandlung in DNF kann exponentiellen Aufwand haben

Question 5

Wenn ein Problem 𝐴 𝑁𝑃-vollständig ist, dann gilt für ein beliebiges 𝑁𝑃-schweres Problem 𝐵:

𝐴 ≤ _𝑝𝑜𝑙 𝐵

Answer 5

Auf ein 𝑁𝑃-schweres Problem lässt sich (nach Definition) jedes Problem aus 𝑁𝑃 in Polynomialzeit reduzieren. Da 𝑁𝑃-vollständige Probleme eine Teilmenge von 𝑁𝑃 bilden, gilt das insbesondere für das Problem 𝐴.

Question 6

Reduktion

Answer 6

A≤B: A ist leichter oder gleich schwer zu lösen wie B

Question 7

BDD (Binary Decision Diagram)

Answer 7

• Das BDD ist der vollständig reduzierte Funktionsgraph.
• Bottom-up
  
  • Verschmelze identische Graphen
  • Eliminiere einen Knoten, falls beide Kanten auf denselben Nachfolger zielen
• Je nach Variablenreihenfolge kann die Kontenanzahl auch für die gleiche Boolesche Funktion unterschiedlich groß sein

Question 8

Lesen Sie aus dem berechneten BDD einen Booleschen Ausdruck in disjunktiver Normalform (DNF) ab.

Answer 8

mit Apostroph = 0

sonst = 1

Question 9

CMOS