Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

NP vs ASP (Reduktion sowie Vollständigkeit)
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> NP vs ASP (Reduktion sowie Vollständigkeit)
 
Autor Nachricht
Wichtelmaus
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 13.01.2011
Beiträge: 1

BeitragVerfasst am: 13 Jan 2011 - 22:34:48    Titel: NP vs ASP (Reduktion sowie Vollständigkeit)

Hallo! Smile

Ich beschäftige mich zur Zeit mit diesem Paper http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf für ein Seminarvortrag.

Mein Thema ist es, nachzuweisen, dass Sudoku in NP liegt. Dies wird hier mittels einer ASP-Reduktion gezeigt, welche folgende Definition hat:

Seien Π_1=(D_1,S_1,σ_1) und Π_2=(D_2,S_2,σ_2) Funktionsprobleme. Eine polynomiale ASP-Reduktion von Π_1 nach Π_2 wird erfüllt von φ=(φ_D,φ_S):
- φ_D ist eine polynomial berechenbare Abbildung von D_1 nach D_2.
- Für alle x ∈ D_1 ist φ_S eine polynomiale Bijektion von σ_1 (x) nach σ_2 (φ_D (x)).

weitere Erklärungen:

Sei Π ein Tripel (D,S,σ) wo folgendes gilt:
- D ist eine Menge von Instanzen von einem Problem.
- S ist eine Menge, welche alle möglichen Lösungen beinhaltet.
- σ ist eine Abbildung von D nach 2^S. Für eine Instanz x∈D, ist σ(x)(⊆S) Lösungsmenge von x und ein Element aus σ(x) heißt Lösung von x.

Hierbei ist noch hinzuzufügen, dass die ASP-Reduktion eine "parsimonious reduction" ist, d.h. sie ist Lösungserhaltend (Anzahl der Lösungen bleibt gleich).
Ich würde nun gern den Bezug zu der polynomialen Reduktion aufweisen wollen, welche wie folgt definiert ist:

Eine Sprache L_1 ⊆ (∑_1)^* heißt polynomial reduzierbar auf eine Sprache L_2 ⊆ (∑_2)^* , falls L_1 ≤ L_2 und die Reduktion f in Polynomialzeit berechenbar ist. Genau heißt das für L_1 und L_2, falls es eine totale Funktion f: (∑_1)^* → (∑_2)^* gibt, für die gilt:
f ist von polynomialer TM-Komplexität, d.h. es gibt eine TM M und eine Schrittzahlfunktion p ∈ poly, so dass M ∀w ∈ ∑^* den Funktionswert f(w) berechnet in ≤ p(|w|) vielen Schritten und
∀x∈∑^*∶(x ∈ L_1 ↔ f(x) ∈ L_2)

Als erstes würde ich aufzeigen, dass bei beiden Reduktionen die Funktionen in Polynomialzeit berechnet werden können und wir eine Abbildung von einem Problem / einer Instanz des Problems auf ein anderes Problem / auf eine Instanz eines anderen Problems abbilden.
Bei der polynomialen Reduktion ist keine Bijektion vorhanden.
Weiß jemand, wie ich dies formell beweisen könnte?

Des Weiteren wird in dem Paper erwähnt, dass die ASP-Vollständigkeit die NP-Vollständigkeit impliziert. Ein Beweis wurde zwar mittels SAT aufgezeigt, aber gibt es vielleicht noch einen anderen Weg, dies zu beweisen, ohne SAT verwenden zu müssen?
ASP-Vollständigkeit habe ich wie folgt definiert:

Ein Funktionsproblem Π ist ASP-vollständig genau dann, wenn Π∈FNP und Π^' ≤_ASP Π für alle Π'∈FNP.

FNP ist eine Klasse, welche aus Funktionsproblemen Π=(D,S,σ) besteht und für die folgendes gilt:
- Es existiert ein Polynom p, so dass gilt |s|≤p(|x|) für beliebige x∈D und beliebige s∈σ(x).
- Für beliebiges x∈D und beliebiges y∈S kann in polynomialer Zeit entschieden werden, ob y∈σ(x).

und die Definition für NP-Vollständigkeit lautet bei mir:

Sei L∈∑^*. L heißt NP-vollständig, falls L ∈ NP-hart und L ∈ NP, d.h. ∀L'∈NP∶L' ≤^poly L.
Sei L∈∑^*. L heißt NP-hart, falls gilt: ∀L'∈NP∶L' ≤^poly L, d.h. alle L' aus NP sind polynomiell reduzierbar auf L.


Ich würde mich freuen, ein paar Tipps zu bekommen, wie ich weiter vorgehen könnte. Smile

Danke schon einmal im Voraus. Wink

Gruß Wichtelmaus
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> NP vs ASP (Reduktion sowie Vollständigkeit)
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum