You are not logged in.

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

41

Tuesday, September 27th 2005, 11:39pm

Das mit 3SAT ist mir auch aufgefallen, habe mich schon gewundert, da es doch NP - Vollständig und somit implizit schon NP - hart ist.

Zum Satz von Cook: Ich würde davon ausgehen, dass du wissen solltest, was es ist und was man damit gezeigt hat. Außerdem ist es sicherlich nicht schlecht, zu wissen, wie man es bewiesen hat, also auf welche Art und Weise. Die genaue Durchführung ist - meiner Meinung nach - zu speziell für die Klausur und steht außerdem ja auch im Skript, welches wie benutzen dürfen.
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

42

Wednesday, September 28th 2005, 9:30am

RE: Satz von Cook

Quoted

Original von KingLifetec
Müssen wir eigentlich den Satz von Cook genau nachvollziehen können?
Also wofür man den brauch ist ja klar, um zu zeigen das SAT NP-Vollständig ist, aber wie man das genau beweist, müssen wir doch sicher nicht wissen oder?
Du solltest ihn zumindest so gut können, daß Du ihn anderen (mit Hilfe des Skriptes) detailliert erklären könntest. Wichtig ist dabei insbesondere, nach welchem Prinzip hier das Verhalten einer TM mit einer aussagenlogischen Formel ausgedrückt wird.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

43

Wednesday, September 28th 2005, 9:32am

Quoted

Original von Markus
Zum Satz von Cook: Ich würde davon ausgehen, dass du wissen solltest, was es ist und was man damit gezeigt hat. Außerdem ist es sicherlich nicht schlecht, zu wissen, wie man es bewiesen hat, also auf welche Art und Weise. Die genaue Durchführung ist - meiner Meinung nach - zu speziell für die Klausur und steht außerdem ja auch im Skript, welches wie benutzen dürfen.
Genau. Niemand wird von euch in der Klausur verlangen, den Beweis mit allen Teilformeln und technischen Details hinzuschreiben. Es könnte jedoch hilfreich sein, das grundsätzliche Vorgehen in diesem Beweis verstanden zu haben.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

44

Wednesday, September 28th 2005, 3:48pm

RE: Fehler im Skript

Quoted

Original von EnteTaylor
Im Skript auf Seite 30 ist ein Fehler (nix schlimmes). Dort steht:

Quoted

Satz: SUBSET-SUM ist NP-vollstäandig.
Beweis: SUBSET-SUM 2 NP wurde schon gezeigt. Wir zeigen nun, dass 3SAT NPhart ist, indem wir 3SAT<=(p m) SUBSET-SUM nachweisen.


Es soll nicht gezeigt werden, dass 3SAT NP-hart ist, sondern dass SUBSET-SUM NP-hart ist.
Danke für den Hinweis, wir haben das Skript intern schon korrigiert.

Die korrigierte Version werden wir jedoch erst nach der Klausur veröffentlichen, um nicht so kurz vorher noch die Teilnehmer der Klausur mit einer neuen (kaum veränderten) Version zu irritieren.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

45

Wednesday, September 28th 2005, 4:32pm

Da hab ich glaube ich auch noch etwas (oder ich habe das falsch verstanden, ist natürlich auch sehr gut möglich ;), und zwar das Königsberger Brückenproblem betreffend. So wird für eben jenes Problem der Multigraph mit Eulerkreis angegeben - aber handelt es sich denn um einen Eulerkreis? Es ist doch eben nicht möglich, alles Brücken genau einmal zu überqueren.
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

zakarumite

Trainee

  • "zakarumite" is male

Posts: 56

Date of registration: Feb 15th 2004

46

Wednesday, September 28th 2005, 5:28pm

hampath

Es gibt noch ein Problem. in dem Skript ist 3SAT auf HAMPATH reduziert. Dafür sind Teilgraphen, und Klauselknoten gezeichnet...usw
Wenn wir
phi = (x1 ODER x2) UND (x1 ODER NOTx2)

definieren, ist eine Belegung mit x1 = 1 X2 = 1 erfüllt, aber gibt es nicht mehr einen Ham.Path von s nach t, weil c1 zwei Mal besucht wird.
Ist das falsch?
...

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

47

Wednesday, September 28th 2005, 5:51pm

Wenn ich dich richtig verstehe:
Das dachte ich zu nächst auch, aber es steht dazu auf S26 "Außerdem werden alle bisher noch nicht besuchten möglichen C_j Teilgraphen durchlaufen, [...]".

Der Algorithmus weiß also, ob eine Klause c_j schon durchlaufen wurde und spart diese entsprechend aus.

Ich hoffe, dass war die richtige Frage zu der Antwort ("42") :P
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

zakarumite

Trainee

  • "zakarumite" is male

Posts: 56

Date of registration: Feb 15th 2004

48

Wednesday, September 28th 2005, 6:03pm

ok, danke!
dann noch eine Frage :)
wenn p = np ist, sind dann alle Sprachen in NP und P auch NP-Vollständig, oder nur die Sprachen, die ausser leer und ganz ... (Ü8) sind NP Vollständig ?
...

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

49

Wednesday, September 28th 2005, 6:06pm

Ich verstehe die Frage nicht so ganz?!
Wenn P = NP, dann sind alle Sprachen in P (und somit auch NP) auch NP-vollständig, außer die leere Sprache und die alles akzeptierende. Das steht doch in Übung 8 (immer diese Sonnenbrillensmilies)
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

50

Wednesday, September 28th 2005, 6:06pm

Quoted

Original von Markus
Da hab ich glaube ich auch noch etwas (oder ich habe das falsch verstanden, ist natürlich auch sehr gut möglich ;), und zwar das Königsberger Brückenproblem betreffend. So wird für eben jenes Problem der Multigraph mit Eulerkreis angegeben - aber handelt es sich denn um einen Eulerkreis? Es ist doch eben nicht möglich, alles Brücken genau einmal zu überqueren.
Du hast recht. Aber so steht es ja auch im Skript. Dort steht sinngemäß, daß das Finden eines Sonntagsspaziergangs, bei dem alle Brücken genau einmal überquert werden, dem Finden eines Eulerkreises in dem angegebenen Multigraphen entspricht.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

51

Wednesday, September 28th 2005, 6:09pm

Äh, ja, da hast du recht, da steht nur, dass es dem entspricht, und nicht dass es einen gibt. Hab ich wohl nicht genau genug gelesen... :evil:
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

snoopy

Junior Schreiberling

  • "snoopy" is male

Posts: 146

Date of registration: Feb 29th 2004

Location: Hannover

Occupation: Informatik

52

Wednesday, September 28th 2005, 7:55pm

Wir hatten zum Schluss in der Übung: Zeige, dass SGI NP-vollständig ist.
Dabei sollte CLIQUE auf SGI reduziert werden. Wie kann man das reduzieren? Ich habe da keinerlei Idee.
Kann mir da jemand helfen?

SGI := { <G1, G2> | G1,G2 Graphen und G1 enthält zu G2 isomorphen Graphen }

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

53

Wednesday, September 28th 2005, 8:59pm

Quoted

Original von snoopy
Wir hatten zum Schluss in der Übung: Zeige, dass SGI NP-vollständig ist.
Dabei sollte CLIQUE auf SGI reduziert werden. Wie kann man das reduzieren? Ich habe da keinerlei Idee.
Kann mir da jemand helfen?

SGI := { <G1, G2> | G1,G2 Graphen und G1 enthält zu G2 isomorphen Graphen }
Reduktionsfunktion:

Eingabe: <G, k>, wobei G ein Graph ist und k eine natürliche Zahl

Ausgabe: <G_1, G_2>, wobei G_1 = G und G_2 ein Graph mit k Knoten ist, die alle direkt miteinander verbunden sind


Jetzt klar? :)
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Hogi

Trainee

  • "Hogi" is male

Posts: 69

Date of registration: Oct 8th 2003

Location: Rinteln

54

Wednesday, September 28th 2005, 9:09pm

ist es vllt folgendes:

- CLIQUE besagt, G enthält vollständigen Teilgraphen X mit mind. k Knoten
- wenn also G und X auf SGI prüfen lasse, dann wird SGI akzeptieren, wenn auch CLIQUE akzeptierte, und SGI wird nicht akzeptieren, wenn auch CLIQUE nicht akzeptierte
- die reduktionsfunktion ist also f(<G,k>) = <G, (vollständiger Graph mit k Knoten)>, (<G,k> im Sinne von CLIQUE)

aber: wie würde man das ganz formal ausdrücken? ich fürchte, dass ich mit dieser ausdrucksweise wertvolle punkte verschenke...

-----

EDIT: hey.. ja... yeah... ich habe es ganz alleine rausgekriegt..

This post has been edited 1 times, last edit by "Hogi" (Sep 28th 2005, 9:10pm)


Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

55

Wednesday, September 28th 2005, 9:44pm

Quoted

Original von Hogi
EDIT: hey.. ja... yeah... ich habe es ganz alleine rausgekriegt..


Omg, ich seh dich schon wieder nach der Klausur im Forum: "Ich hab da ne 1 hinter meine Matrikelnummer, aber ich weiß gar nicht, was das bedeutet" ;) :D :P
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

EnteTaylor

Trainee

  • "EnteTaylor" is male

Posts: 111

Date of registration: Oct 24th 2003

Location: Göttingen

Occupation: weil's toll is

56

Wednesday, September 28th 2005, 10:04pm

kann man es denn allgemein so machen, dass man die Definition des np-vollständigen Problems, das reduziert werden soll (in diesem Fall also CLIQUE) hernimmt und irgendwie versucht, daraus das andere Problem zusammenzubasteln (hier SGI) ?
Meine Gedächtnisprotokolle: www.janwy.de

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

57

Wednesday, September 28th 2005, 10:54pm

Quoted

Original von EnteTaylor
kann man es denn allgemein so machen, dass man die Definition des np-vollständigen Problems, das reduziert werden soll (in diesem Fall also CLIQUE) hernimmt und irgendwie versucht, daraus das andere Problem zusammenzubasteln (hier SGI) ?
Nein, das ist nur eine von vielen Möglichkeiten. Aber es läßt sich in der Tat häufig ein NP-vollständiges Problem finden, das man auf das zu untersuchende Problem reduzieren kann und das wie hier einen Spezialfall dieses Problems darstellt (denn CLIQUE ist ja wie die obige Reduktion zeigt ein Spezialfall von SGI).
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

snoopy

Junior Schreiberling

  • "snoopy" is male

Posts: 146

Date of registration: Feb 29th 2004

Location: Hannover

Occupation: Informatik

58

Thursday, September 29th 2005, 9:30am

Quoted

Original von Joachim

Quoted

Original von snoopy
SGI := { <G1, G2> | G1,G2 Graphen und G1 enthält zu G2 isomorphen Graphen }
Reduktionsfunktion:

Eingabe: <G, k>, wobei G ein Graph ist und k eine natürliche Zahl

Ausgabe: <G_1, G_2>, wobei G_1 = G und G_2 ein Graph mit k Knoten ist, die alle direkt miteinander verbunden sind

Jetzt klar? :)


Nein :(

Müsste die Ausgabe dann nicht komplett SGI abdecken?
Aber es gibt doch auch isomorphe Teilgraphen, die weit von einer Clique entfernt sind, z.B. ein Wald 1-elem. Bäume kann doch auch Teilgraph sein...
irgendwie versteh ich das System hier nicht

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

59

Thursday, September 29th 2005, 9:34am

Quoted

Original von snoopy

Quoted

Original von Joachim

Quoted

Original von snoopy
SGI := { <G1, G2> | G1,G2 Graphen und G1 enthält zu G2 isomorphen Graphen }
Reduktionsfunktion:

Eingabe: <G, k>, wobei G ein Graph ist und k eine natürliche Zahl

Ausgabe: <G_1, G_2>, wobei G_1 = G und G_2 ein Graph mit k Knoten ist, die alle direkt miteinander verbunden sind

Jetzt klar? :)


Nein :(

Müsste die Ausgabe dann nicht komplett SGI abdecken?
Aber es gibt doch auch isomorphe Teilgraphen, die weit von einer Clique entfernt sind, z.B. ein Wald 1-elem. Bäume kann doch auch Teilgraph sein...
irgendwie versteh ich das System hier nicht
Bei m-Reduktionen (A <= B) geht es darum, jedem Wort aus A ein Wort aus B zuzuordnen; jedem Wort, das nicht in A liegt, hingegen ein Wort, das nicht in B liegt.

Gehört <G, k> nun zu CLIQUE, so gibt es einen vollständigen Teilgraphen der Größe k in G. Also ist <G_1, G_2> (siehe oben) in SGI.

Gehört <G, k> nicht zu CLIQUE, so gibt es auch keinen vollständigen Teilgraphen der Größe k in G. Also ist <G_1, G_2> nicht in SGI.

Damit hat man gezeigt, daß SGI NP-vollständig ist. Da es in NP liegt gilt: Wäre es nicht NP-vollständig, so wäre auch CLIQUE aufgrund der angegebenen Reduktion nicht NP-vollständig. Aber CLIQUE ist ja NP-vollständig, was zum Widerspruch führt. Also folgt: SGI ist NP-vollständig.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 2 times, last edit by "Joachim" (Sep 29th 2005, 9:36am)


kritop

Junior Schreiberling

  • "kritop" is male

Posts: 223

Date of registration: Sep 22nd 2003

Location: Bochum

60

Thursday, September 29th 2005, 9:43am

Hab ich für eine Kombiklausur eigentlich einen neuen Freiversuch, auch wenn ich das eine Fach schon einmal geschrieben habe, in diesem Fall Theo. Inf.?
Wer es gelernt hat, sich von der Herrschaft des Ärgers zu befreien, wird das Leben viel lebenswerter finden. Bertrand Russel