Nichtdet. polynomiell < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:51 Do 27.04.2006 | | Autor: | Pollux |
| Aufgabe | a) Man schreibe das Erfüllbarkeitsproblem der Aussagenlogik als Wortproblem:
Gegeben: Aussagenlogische Formel "AL"
Gefragt: ist "AL" erfüllbar?
b) Warum gehört das Erfüllbarkeitsproblem zur Komplexitätsklasse Nichtdeterministisch polynomiell (NP)? |
Hallo,
in der obigen Aufgabenstellung ist vom Erfüllbarkeitsproblem der Aussagenlogik die Rede, welches im Folgenden (Gegeben..., Gesucht...) skizziert wird! Dies soll nun als Wortproblem geschrieben werden. Ich hab mir dabei folgendes überlegt:
Es sei eine aussagenlogische Formel AL gegeben. Dann ist gesucht ob
[mm] AL\in\{A| \exists \alpha: \alpha(A)=wahr\} [/mm] , d.h. ist AL in der Menge aller Aussagenlogischen Formeln für die eine Belegung existiert, so dass AL als wahr ausgewertet wird. Ist das so richtig?
Bei der zweiten Frage (NP) habe ich, leider keine Ahnung. Nichtdeterministisch bedeutet ja, dass (in diesem Fall) bei der Auswertung nicht jeder Schritt festgelegt ist. Aber ist die Auswertung nicht eindeutig bestimmt?!
mfg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:21 Fr 28.04.2006 | | Autor: | Frank05 |
> Hallo,
Hallo,
> in der obigen Aufgabenstellung ist vom
> Erfüllbarkeitsproblem der Aussagenlogik die Rede, welches
> im Folgenden (Gegeben..., Gesucht...) skizziert wird! Dies
> soll nun als Wortproblem geschrieben werden. Ich hab mir
> dabei folgendes überlegt:
> Es sei eine aussagenlogische Formel AL gegeben. Dann ist
> gesucht ob
> [mm]AL\in\{A| \exists \alpha: \alpha(A)=wahr\}[/mm] , d.h. ist AL in
> der Menge aller Aussagenlogischen Formeln für die eine
> Belegung existiert, so dass AL als wahr ausgewertet wird.
> Ist das so richtig?
Nicht wirklich. Zum einen willst du [mm]\subset[/mm] und nicht [mm]\in[/mm] und zum anderen bleibt immer noch die Frage was ist A? Bei einem Wortproblem liegt ja immer ein Alphabet [mm]\Sigma[/mm] zu Grunde.. wie geht dieses hier mit ein?
> Bei der zweiten Frage (NP) habe ich, leider keine Ahnung.
> Nichtdeterministisch bedeutet ja, dass (in diesem Fall) bei
> der Auswertung nicht jeder Schritt festgelegt ist. Aber ist
> die Auswertung nicht eindeutig bestimmt?!
Nein die ist nicht eindeutig bestimmt beim Nichtdeterminismus. Sieh dir nochmal das Konzept NichtDet. genauer an in Bezug auf Turing-Maschinen. Es geht darum, ob ein akzeptierender Berechnungspfad existiert. Eine 'Auswertung' als solche ist uninteressant und von daher auch die Reihenfolge. Intuitiv ist klar, dass es nicht eindeutig ist, wenn du z.B. eine Formel F betrachtest, die für 2 versch. Eingaben wahr ist. Dann kann nichtdet. die eine oder andere Eingabe gefunden werden. Wichtig ist wiederum nur, dass es so eine Eingabe gibt (denn dann ist [mm]F \in SAT[/mm]) und nicht welche nun genau gefunden wurde.
Lies am besten nochmal das Kapitel zu Nichtdeterminismus in deinem Skript nach (oder einem bel. Buch über theoretische Informatik) und zum zweiten Teil findest du einiges im Beweis von Cook zur NP-Vollständigkeit von SAT.
hth,
Frank
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:14 Fr 28.04.2006 | | Autor: | Pollux |
Hallo,
Zum Wortproblem:
Ein Wort w löst ja, soweit ich das verstanden habe, das Wortproblem, wenn w in einer Sprache L liegt. In der ersten Teilaufgabe heißt es, dass eine Aussagenlogische Formel gegeben ist und es ist gesucht, ob sie erfüllbar ist. In einem Skript habe ich gelesen, dass eine aussagenl. Formel erfüllbar heißt, falls ein Modell von ihm existiert, dass also eine Belegung existiert, so dass diese aussagenlogische Formel als wahr ausgewertet wird. Als "A" bezeichne ich die Menge aller Aussagenlogischen Formeln (Also Wörter, wenn man so will, über dem Alphabet , welches aus [mm] {\wedge,\vee, ...} [/mm] sowie sogenannten Aussagenzeichen besteht). Und der Rest ist der obigen Definition nachempfungen. Daher kann ich nicht verstehen, warum das nicht stimmt.
Zu Nichtdet. Polynomiell:
In unserem Skript steht nur eine (ausführliche) Erläuterung: Anzahl der Rechenschritte hängt nichtdeterministisch polynomiell von der Eingabenlänge ab.
Darunter verstehe ich, dass man bei Eingaben gleicher Länge, unterschiedlich viele Rechenschritte erhalten kann (eben nichtdet.)
In dem Buch, das uns empfohlen wurde, steht hiervon auch nichts drin (leider). Von Turingmaschinen und SAT habe ich auch noch nichts gehört.
Trotzdem, danke für die Antwort!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:23 Fr 28.04.2006 | | Autor: | Frank05 |
> Hallo,
Hallo nochmal,
> Zum Wortproblem:
> Ein Wort w löst ja, soweit ich das verstanden habe, das
> Wortproblem, wenn w in einer Sprache L liegt. In der ersten
> Teilaufgabe heißt es, dass eine Aussagenlogische Formel
> gegeben ist und es ist gesucht, ob sie erfüllbar ist. In
> einem Skript habe ich gelesen, dass eine aussagenl. Formel
> erfüllbar heißt, falls ein Modell von ihm existiert, dass
> also eine Belegung existiert, so dass diese
> aussagenlogische Formel als wahr ausgewertet wird. Als "A"
> bezeichne ich die Menge aller Aussagenlogischen Formeln
> (Also Wörter, wenn man so will, über dem Alphabet , welches
> aus [mm]{\wedge,\vee, ...}[/mm] sowie sogenannten Aussagenzeichen
> besteht). Und der Rest ist der obigen Definition
> nachempfungen. Daher kann ich nicht verstehen, warum das
> nicht stimmt.
Das war vielleicht etwas unklar. Was du hier sagst stimmt schon, nur in deiner vorigen Lösung stand lediglich 'A'. Ohne Angaben dazu, was das nun genau sein soll. Und wie gesagt deine Menge AL ist eine Teilmenge der angegebenen Menge und nicht ein Element dieser Menge (genaugenommen definierst du AL ja damit und hast somit sogar Gleichheit).
> Zu Nichtdet. Polynomiell:
> In unserem Skript steht nur eine (ausführliche)
> Erläuterung: Anzahl der Rechenschritte hängt
> nichtdeterministisch polynomiell von der Eingabenlänge ab.
> Darunter verstehe ich, dass man bei Eingaben gleicher
> Länge, unterschiedlich viele Rechenschritte erhalten kann
> (eben nichtdet.)
> In dem Buch, das uns empfohlen wurde, steht hiervon auch
> nichts drin (leider). Von Turingmaschinen und SAT habe ich
> auch noch nichts gehört.
Normalerweise wird dieses Konzept mit Turingmaschinen oder Automaten eingeführt. Wenn das wirklich alles ist, was in eurem Skript und dem empfohlenen Buch steht, dann wünsch ich dir schonmal viel Spaß bei der rituellen Bücherverbrennung 
http://de.wikipedia.org/wiki/Nichtdeterminismus bietet eine gut lesbare Einführung. Ansonsten kann ich dir z.B. die Bücher von Prof. Schöning empfehlen.
SAT (von Satisfiability = Erfüllbarkeit) ist lediglich die geläufigere Bezeichnung für die erfüllbaren aussagenlogischen Formeln. Du hast die Menge in deiner Lösung einfach nur AL genannt.
> Darunter verstehe ich, dass man bei Eingaben gleicher
> Länge, unterschiedlich viele Rechenschritte erhalten kann
> (eben nichtdet.)
Da hast du sehr wahrscheinlich eine falsche Vorstellung von Nichtdeterminismus. Es kann unterschiedliche Laufzeiten geben, allerdings nur bis zu einem konstanten Faktor. Die polynomielle Laufzeit bleibt prinzipiell erhalten. Worum es beim Nichtdeterminismus geht ist der Unterschied in den verwendeten Rechenschritten (nicht unbedingt in ihrer Anzahl).
Beispiel: In deiner Formel taucht x auf. Dein Algorithmus probiert einfach alle möglichen Belegungen aus und versucht somit die Formel zu erfüllen. Beginnt der Algorithmus nun x=0 oder x=1 zu testen? Deterministisch kannst du diese Frage eindeutig beantworten. Nichtdeterministisch wird der Algorithmus jedoch immer sofort die 'richtige' Wahl treffen, d.h. wenn die Formel für x=0 wahr wird, dann wählt dein Algorithmus auch x=0 und analog für x=1. Somit benötigt er auch nur einen Rechenschritt um x korrekt zu belegen (was auch ein wenig verdeutlicht, warum nichtdeterministisch scheinbar mehr kann -- ein offenes Problem [P=NP?]).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:28 Fr 28.04.2006 | | Autor: | Frank05 |
> Und wie
> gesagt deine Menge AL ist eine Teilmenge der angegebenen
> Menge und nicht ein Element dieser Menge (genaugenommen
> definierst du AL ja damit und hast somit sogar
> Gleichheit).
Hoppla. Entschuldige, das geht auf meine Kappe. Ich hab wohl überlesen, dass bei dir AL nur eine Formel sein soll. Sorry.
Dementsprechend passt deine ursprüngliche Lösung, wenn du noch angibst, was A ist.
|
|
|
|
.
