Frage zur NP vs. P Problematik

[Senior Sanchez]

Hoi,

Also meine Frage ist ansich ganz einfach:

Das Problem des kürzesten Pfades in einem gewichteten Graph liegt ja bekanntlich in P.
Warum liegt aber das Problem des längsten Pfades in NP?

Ich gebe zu, ich habe nicht probiert da was zu programmieren oder auszuprobieren, nur ich frage mich, wo da jetzt eigentlich das Problem sein soll?

Sind beim längsten Pfad eigentlich Zyklen erlaubt? Das wäre aber ansich ja schwachsinnig, weil der Pfad dann unendlich lang sein könnte.

[Unfug]

Also ich stell mir das so vor:
kürzester Pfad:
Du hast sagen wir mal einen Pfad der Länge 2. Dann brauchst Du ja nur noch zu gucken, welche Pfade maximal 2 sind. Alles darüber braucht man ja nicht mehr durchzulaufen. (Break ; )

Bei dem längsten Pfad dagegen muss man ja sämtliche Pfade bis zum Ende durchlaufen. Und wenn jeder dieser Pfade nun ne Millionen lange Pfade hat ist das natürlich schon gaaanz schön lang.


Edit:
Man sollte das Ganze noch abstrakter , theoretischer betrachten. Ähnlich wie mit den Hanoi Türmen. 3 Scheiben kann man noch relativ flott lösen, aber was ist 64 Scheiben? Ich hab mal gelesen, daß man dafür 1 Billionen Jahre bräuchte, wenn man jede Sekunde eine verschiebt. Und da bei dem obrigen (bei meinem Beispiel) die Grenze 2 ist, ist es natürlich vieeel weniger, als wenn man komplette Pfade durchgeht (die ja sehr lang sein könnten)

[Monger]

So würde ich das auch sehen. Wenn du nach dem kürzesten Pfad suchst, kannst du alle Pfade ignorieren, die länger sind als der bisher kürzeste Pfad.
Wenn also dein aktuell kürzester Pfad bei 4 Knoten ist, kannst du jeden anderen Pfad spätestens ab dem 4ten Knoten ignorieren.


Für den längsten Pfad musst du aber jeden Pfad bis zum Ende durchgehen. Ich bin grad unfähig es durchzurechnen, aber rein gefühlsmäßig kann das schon durchaus im nicht-polynomialen Raum liegen.

[Trap]

Bei NP vs. P Sachen muss man ganz genau auf Details achten.

Zuerst mal ist NP-vollständig nur für Entscheidungsprobleme definiert. Damit muss das Problem so formuliert werden: Gibt es einen einfachen Pfad von A nach B mit mindestens x Knoten im Graph G?

Man könnte jetzt noch Beweisen, dass das NP-vollständig ist, das bringt aber selten irgendwelche Einsichten, die über "x ist NP-vollständig" hinausgehen.

Abstrakter betrachtet muss man beim kürzesten Pfad eine monoton wachsende Größe minimieren, beim längsten Pfad eine monoton wachsende Größe maximieren. Da ist klar, dass es im 2. Fall mehr Spielraum gibt und mehr in Frage kommende Konfigurationen.

Achso, was man noch immer im Kopf haben sollte:
Es gibt eigentlich 3 Problemklassen, die man normalerweise behandelt, die für die man einen Algorithmus in P kennt, die für die man keinen in P kennt (die aber Berechenbar sind) und die für die man Beweisen kann, dass sie NP-vollständig sind.

[Stone2001]

Sind beim längsten Pfad eigentlich Zyklen erlaubt? Das wäre aber ansich ja schwachsinnig, weil der Pfad dann unendlich lang sein könnte.
Nimmt doch nur mal an, dass in dem Graphen keine Zyklen vorhanden sind. Dann kannst du dir aus dem Graphen einen Baum konstruieren, dessen Wurzel der Startpunkt und dessen Blätter der Zielpunkt darstellen. Jeder Zweig stellt nun eine Möglichkeit dar vom Startpunkt zum Zielpunkt zu kommen. Bei einem Baum der Höhe n sind das nun mal 2^n verschiedene Zweige.
Jetzt mußt du nur noch den richtigen Zweig finden. Im deterministischen Fall bleibt dir nichts anderes übrig, als alle Zweige durchzugehen und die Geweichte zusammen zu zählen. Im nichtdeterministischen Fall, läßt du das Orakel einfach den längsten Weg ausspucken. ;) => NP-Problem! (es sei denn du findest eine Möglichkeit aus 2^n Zweigen den richtigen Zweig in poly. Zeit zu finden)

Ist das Problem NP-Vollständig? Ich könnte mir gerade schon einen Reduktionsbeweis auf TSP (ö.ä.) vorstellen.

[Senior Sanchez]

Bei NP vs. P Sachen muss man ganz genau auf Details achten.

Zuerst mal ist NP-vollständig nur für Entscheidungsprobleme definiert. Damit muss das Problem so formuliert werden: Gibt es einen einfachen Pfad von A nach B mit mindestens x Knoten im Graph G?

Man könnte jetzt noch Beweisen, dass das NP-vollständig ist, das bringt aber selten irgendwelche Einsichten, die über "x ist NP-vollständig" hinausgehen.

Abstrakter betrachtet muss man beim kürzesten Pfad eine monoton wachsende Größe minimieren, beim längsten Pfad eine monoton wachsende Größe maximieren. Da ist klar, dass es im 2. Fall mehr Spielraum gibt und mehr in Frage kommende Konfigurationen.

Stimmt, danke für den Hinweis mit den Entscheidungsproblemen.

Edit: Allgemein wird das doch gar nicht so eingehalten, oder? Zum Beispiel wird ja beim TSP oft gesagt, dass es NP-Vollständig ist, aber das nicht als Entscheidungsproblem inform einer Frage formuliert, oder?

@Stone2001

Danke für die Erklärung, ist mir auch soweit alles klar, aber wie kommst du auf eine Höhe von 2^n?

EDIT: Hat sich gerade geklärt, hatte nen Paul.

[Senior Sanchez]

Ich hätte gleich noch ne Frage, die durch ein Dokument bei mir aufgeworfen wurde, welches ich las.

Ist es rein theoretisch möglich, dass ein Computerprogramm jedes andere auf Korrektheit überprüfen kann?

Die Frage blieb da etwas unbeantwortet und ich weiß die Antwort nicht, ich würde aber mal auf Nein tippen, da das bestimmt mit dem Halteproblem zusammenhängt. Aber kann das jemand näher begründen?

[Monger]

Ist es rein theoretisch möglich, dass ein Computerprogramm jedes andere auf Korrektheit überprüfen kann?


Hrm... irgendwie kommt mir das alles unglaublich bekannt vor. Erschreckend, wieviel man von den ganzen Vorlesungen innerhalb ein paar Monate vergessen kann...


IIRC nein. Argumentativ lief das darauf hinaus, dass zu jedem Wahrheitskriterium sich ein Simulator finden lässt. Wenn ich an einem Programm die Werte X, Y, Z betrachte, kann das diese Werte immer so hinbiegen dass sie für mich als gültig darstehen, und intern trotzdem was ganz anderes machen. Mit einem Wrapper kann man jede Prüfung auf Korrektheit unterlaufen...

So oder ähnlich war der Gedankengang.

[Senior Sanchez]

Hrm... irgendwie kommt mir das alles unglaublich bekannt vor. Erschreckend, wieviel man von den ganzen Vorlesungen innerhalb ein paar Monate vergessen kann...


IIRC nein. Argumentativ lief das darauf hinaus, dass zu jedem Wahrheitskriterium sich ein Simulator finden lässt. Wenn ich an einem Programm die Werte X, Y, Z betrachte, kann das diese Werte immer so hinbiegen dass sie für mich als gültig darstehen, und intern trotzdem was ganz anderes machen. Mit einem Wrapper kann man jede Prüfung auf Korrektheit unterlaufen...

So oder ähnlich war der Gedankengang.

Wirklich? Na das ist ja ne abstruse Begründung.

[Trap]

Bei Beweissystemen hätte man gern 3 Eigenschaften:
-vollständig (jede wahre Aussage ist herleitbar)
-korrekt (es lassen sich nur wahre Aussagen herleiten, auch widerspruchfrei genannt)
-effizient berechenbar

Wie so oft bekommt man die aber nicht ;)

Gegen die Vollständigkeit spricht Gödels Unvollständigkeitssatz, zumindest bei ausdrucksstarken Systemen. Korrektheit bekommt man hin, ab und zu zumindest ;D

Effizient berechenbar nur bei weiterer Einschränkung der herleitbaren Aussagen (oder Einschränkung der Programmiersprache). Um zu zeigen, dass ein Programm korrekt ist, muss man nämlich bei interessanten Programmen einen Terminierungsbeweis führen und das geht immer nur in ein paar Sonderfällen, einen allgemeinen Beweiser dafür kann es nicht geben, siehe Halteproblem.

[Senior Sanchez]

Bei Beweissystemen hätte man gern 3 Eigenschaften:
-vollständig (jede wahre Aussage ist herleitbar)
-korrekt (es lassen sich nur wahre Aussagen herleiten, auch widerspruchfrei genannt)
-effizient berechenbar

Wie so oft bekommt man die aber nicht ;)

Gegen die Vollständigkeit spricht Gödels Unvollständigkeitssatz, zumindest bei ausdrucksstarken Systemen. Korrektheit bekommt man hin, ab und zu zumindest ;D

Effizient berechenbar nur bei weiterer Einschränkung der herleitbaren Aussagen (oder Einschränkung der Programmiersprache). Um zu zeigen, dass ein Programm korrekt ist, muss man nämlich bei interessanten Programmen einen Terminierungsbeweis führen und das geht immer nur in ein paar Sonderfällen, einen allgemeinen Beweiser dafür kann es nicht geben, siehe Halteproblem.

Ahhh, ich verstehe.

Eine Programmüberprüfung muss somit immer überprüfen ob das zu testende Programm terminiert und das beißt sich ja bekanntlich mit dem Halteproblem.

[Senior Sanchez]

Und noch eine Frage, weil sie so schön reinpasst ;)

Es geht um NP-hart und NP-Vollständig. Bisher habe ich immer nur recht schwammige Definitionen von NP-hart gefunden, außer eine.

"P ist eine Teilmenge von NP. Ob P gleich NP ist oder nicht, ist eines der großen ungelösten Probleme der Informatik. Es gibt eine Reihe von Problemen in NP, von denen nicht bekannt ist, ob sie auch in P liegen. Einige von diesen Problemen hängen in dem folgenden Sinn miteinander zusammen: wenn man auch nur von einem dieser Probleme zeigen könnte, dass es in P liegt, wären die anderen auch alle in P. Probleme mit dieser Eigenschaft bezeichnet man als NP-hart. Probleme, die in NP liegen und NP-hart sind, heißen NP-vollständig."

Ist das so richtig?
Sprich, wenn ein Problem X auf ein Problem in NP per Polynomialzeitreduktion abgebildet werden kann ist es NP-Hart. Liegt Problem X dazu noch in NP, dann ist es NP-Vollständig.

Kennt da jemand ganz spontan ein NP-hartes Problem, das nicht NP-vollständig ist?

[HajottV]

Kennt da jemand ganz spontan ein NP-hartes Problem, das nicht NP-vollständig ist?

Das Halteproblem HP für Turingmaschinen.

1) HP nicht NP-vollständig:

Da das Halteproblem nicht entscheidbar ist, kann HP nicht in NP liegen.

2) SAT in P reduzierbar auf HP:

Zu der Eingabe F aus SAT kann man in polynomieller Zeit (!) ein Programm
P erzeugen, das folgendes macht: Es testet sukzessive alle Belegungen der
Variablen in F und terminiert, wenn es eine Lösung findet. Ansonsten
fängt es wieder von vorne an.

P terminiert <=> F ist erfüllbar

Gruß

Jörg

[Senior Sanchez]

Das Halteproblem HP für Turingmaschinen.

1) HP nicht NP-vollständig:

Da das Halteproblem nicht entscheidbar ist, kann HP nicht in NP liegen.

2) SAT in P reduzierbar auf HP:

Zu der Eingabe F aus SAT kann man in polynomieller Zeit (!) ein Programm
P erzeugen, das folgendes macht: Es testet sukzessive alle Belegungen der
Variablen in F und terminiert, wenn es eine Lösung findet. Ansonsten
fängt es wieder von vorne an.

P terminiert <=> F ist erfüllbar

Gruß

Jörg

Klingt logisch, danke :)

Also ist die Definition korrekt, oder?

[Stone2001]

Die Definition ist korrekt, ja (siehe z.B: Schöning - Theoretishe Informatik S. 157)! Aber nicht die einzige...