Algorithmus transformieren ...
-
MisterX schrieb:
Aber wenn man Glück hat hat man gerade eine Instanz bei der eben doch ein Polynomialzeitalgorithmus existieren kann.
Genau ein berühmtes Beispiel für eine einfache Instanz eines NP-harten Problems ist: Geld. Nämlich: welche Geldscheine/stücke muss man geben um den Preis exakt zu bezahlen. Lösen wir tagtäglich im Kopf aber andere Instanzen des Problems sind kaum lösbar.
-
Ich nehme an mit NP-hart meinst du NP-schwer.
otze schrieb:
MisterX schrieb:
Aber wenn man Glück hat hat man gerade eine Instanz bei der eben doch ein Polynomialzeitalgorithmus existieren kann.
Genau ein berühmtes Beispiel für eine einfache Instanz eines NP-harten Problems ist: Geld. Nämlich: welche Geldscheine/stücke muss man geben um den Preis exakt zu bezahlen.
Dieses Problem ist nicht NP-schwer, wenn es darum geht, eine minimale Anzahl an Scheinen/Münzen zu finden um einen gegebenen Betrag zu bezahlen. Denn das ist eine Variante des eindimensionalen Rucksack-Problemn mit ganzzahligen Gewichten. Unter diesen Voraussetzungen existiert ein dynamic-programming-Algorithmus, der in Polynomialzeit läuft.
Wenn es nur darum geht, irgendeine einigermaßen gute Möglichkeit zu finden, einen gegebenen Geld-Betrag zu bezahlen, wird es noch einfacher: Dafür reicht ein Greedy-Algorithmus wie "nimm immer den aktuell größtmöglichen Schein/Münze". Möglicherweise löst dieser Greedy-Algorithmus das Problem sogar optimal im Sinne von "minimale Anzahl an Scheinen/Münzen für vorgegebenen Betrag" für den Fall "Währung = Euro".
MisterX schrieb:
Aber wenn man Glück hat hat man gerade eine Instanz bei der eben doch ein Polynomialzeitalgorithmus existieren kann.
Für einzelne Instanzen existiert immer ein Polynomialzeit-Algorithmus, aber das ist eher trivial. Beweis: Angenommen für die konkrete Instanz ist die Antwort "ja". Dann ist ein Polynomialzeit-Algorithmus, der diese Instanz löst:
return "yes"Daher denk ich, "für eine bestimmte Instanz existiert ein Polynomialzeitalgorithmus" ist keine hilfreiche Aussage. Eine ganze Klasse von Instanzen, die in Polynomialzeit lösbar sind, wär interessanter.
Der Algorithmus, den du beschrieben hast, löst aber sämtliche Probleminstanzen, nicht nur manche. Das ist ein ganz normaler Algorithmus, der das Entscheidungs-Problem "vertex cover" in seiner Allgemeinheit löst und dabei für die Ja-Antwort sogar ein Zertifikat konstruieren kann, nämlich das vertex cover selbst.
Ob die Laufzeit exponentiell oder polynomiell ist, hängt davon ab, ob k Teil der Eingabe ist oder nicht. Falls k nicht Teil der Eingabe ist, ist die Laufzeit polynomiell, sonst exponentiell.
MisterX schrieb:
1. O(k*n) (Adjazensliste durchlaufen jeweils bis maximal Knoten k)
[...]
Also ist die Laufzeit unabhängig von der Knoten und Kantenanzahl des Graphen!!!Wenn Schritt 1 schon O(k*n) ist, wie kann dann bei der Gesamtlaufzeit der Faktor n wegfallen? So wie ich das sehe, ist die Laufzeit von der Zahl der Knoten im Eingabegraph abhängig, nicht aber von der Zahl der Kanten. Das ist aber im Prinzip erstmal nicht überraschend, denn die Zahl der Kanten hängt bei jedem Graphen nur polynomiell von der Zahl seiner Knoten ab. Wenn die Laufzeit aber nur linear von der Zahl der Knoten abhängt, das ist schon viel besser (das scheint hier der Fall zu sein).
-
Christoph schrieb:
Dieses Problem ist nicht NP-schwer, wenn es darum geht, eine minimale Anzahl an Scheinen/Münzen zu finden um einen gegebenen Betrag zu bezahlen.
subset-sum ist np-vollständig. Es ging um den exakten Betrag, nicht die minimale Anzahl Scheine/Geldstücke.
-
Ist das Subset-Sum? Immerhin hat man nur sehr wenige verschiedene Münztypen.
-
Michael E. schrieb:
Ist das Subset-Sum? Immerhin hat man nur sehr wenige verschiedene Münztypen.
Stimmt, das ist nicht subset-sum. Der maximale Wert eines Scheins ist auf 500 Euro beschränkt, damit ist das Problem in Polynomialzeit lösbar. subset-sum wird erst NP-vollständig, wenn man keine Schranken für die auftretenden Zahlen hat.
-
Bashar schrieb:
Ist das nicht trivial? Jede Turingmaschine, die zu N Strichen im Eingabeband 2^N Striche im Ausgabeband malen soll, benötigt doch Ω(2^N) Schritte.
Ganz so trivial ist es nicht. In P bzw. EXP liegen keine Turingmaschinen, sondern Entscheidungsprobleme. Die Antwort darf also nur ein kurzes "ja" oder "nein" sein, so einfach mit der Kodierung tricksen ist nicht erlaubt.
Die Beweisidee für P != EXP ist aber ein ziemlich schönes Diagonalisierungsargument, das ich bisher auch nicht kannte, deswegen möchte ich die kurz vorstellen. (Beweis aus dem Buch "Computational Complexity" von S. Arora und B. Barak, es ist ein Spezialfall des allgemeineren "time hierarchy theorem").
Sei D eine deterministische Turingmaschine, die auf der Eingabe x der Länge n folgendes macht (x ist eine natürliche Zahl):
1. Für die ersten 2^n Schritte von
Simuliere M_x auf der Eingabe x, wobei M_x die durch x kodierte Turingmaschine ist.
2. Falls bei der Simulation ein Bit b als Ergebnis geschrieben wurde, gibt 1-b aus, sonst 0.Damit ist D eine Turingmaschine, die in O(2^n) läuft, denn Zeile 1 benötigt genau 2^n Schritte, und Zeile 2 benötigt nur eine konstante Anzahl Schritte.
Angenommen P = EXP. Dann gibt es eine (andere) Turingmaschine M, die das gleiche wie D macht, nur effizienter. Genauer gesagt, die Turingmaschine M kann genau das, was D macht, in Laufzeit c*n^k machen für Konstanten c, k > 0. Jetzt kommt das Diagonalisierungsargument: Was passiert, wenn man M als Eingabe sich selbst gibt? Sei m eine Kodierung der Turingmaschine M als natürliche Zahl.
M(m) ist nach Definition von M das gleiche wie D(m). Was D(m) macht, steht oben: Es simuliert die Maschine M genau 2^|m| Schritte lang auf der Eingabe m. Wenn man m nur groß genug wählt (warum man das kann, siehe unten), dann kann die Turingmaschine D in 2^|m| Schritten c*|m|^k Schritte der Turingmaschine M simulieren. Nach c*|m|^k Schritten ist die Turingmaschine M aber schon fertig, nach Konstruktion von M. Also wird D nun in Zeile 2 des Pseudocodes oben das Bit M(m) vorfinden und folglich 1-M(m) ausgeben. Was wir gerade berechnet haben, war aber D(m), und das ist dasselbe wie M(m). Also hat man M(m) = 1-M(m), ein Widerspruch.
Daraus folgt P != EXP.
Warum man m so groß wählen kann, dass man in 2^|m| Schritten c*|m|^k Schritte der durch m kodierten Turingmaschine simulieren kann?
1. Für jede Turingmaschine gibt es beliebig lange Kodierungen, denn man kann immer überflüssige Zustände hinzufügen.
2. Für eine feste Turingmaschine kann man n Schritte dieser Turingmaschine simulieren in O(n log n), dafür gibt es konkrete Algorithmen. Der Simulationsoverhead ist also nur logarithmisch und damit klein genug, dass er hier nicht stört.
-
MisterX schrieb:
1. O(k*n) (Adjazensliste durchlaufen jeweils bis maximal Knoten k)
[...]
Also ist die Laufzeit unabhängig von der Knoten und Kantenanzahl des Graphen!!!Wenn Schritt 1 schon O(k*n) ist, wie kann dann bei der Gesamtlaufzeit der Faktor n wegfallen? So wie ich das sehe, ist die Laufzeit von der Zahl der Knoten im Eingabegraph abhängig, nicht aber von der Zahl der Kanten. Das ist aber im Prinzip erstmal nicht überraschend, denn die Zahl der Kanten hängt bei jedem Graphen nur polynomiell von der Zahl seiner Knoten ab. Wenn die Laufzeit aber nur linear von der Zahl der Knoten abhängt, das ist schon viel besser (das scheint hier der Fall zu sein).
Stimmt. Es ist noch linear in n.
Aber nur in Bezug auf k exponentiell und bei kleinem, konstanten k eben polynomiell.
-
Eine Anmerkung noch:
k-Vertex-Cover geht noch mal deulich schneller mit O(n * 3^k * k^2)
(Algorithmus von Papadimitriou).Es bleibt aber bei Exponentiell bei Berücksichtigung von k und sonst Polynomiell.
-
Christoph schrieb:
Bashar schrieb:
Ist das nicht trivial? Jede Turingmaschine, die zu N Strichen im Eingabeband 2^N Striche im Ausgabeband malen soll, benötigt doch Ω(2^N) Schritte.
Ganz so trivial ist es nicht. In P bzw. EXP liegen keine Turingmaschinen, sondern Entscheidungsprobleme. Die Antwort darf also nur ein kurzes "ja" oder "nein" sein, so einfach mit der Kodierung tricksen ist nicht erlaubt.
Sowas ähnliches ging mir direkt nach dem Abschicken auf, aber da der OP nach einem Algorithmus für die Erzeugung der n-ten Fibonacci-Zahl gefragt hat, hab ich es stehen lassen.
-
Michael E. schrieb:
Ist das Subset-Sum? Immerhin hat man nur sehr wenige verschiedene Münztypen.
naja, ich halte es für eine Instanz von Subset-Sum die polynomiell lösbar ist. Das war ja eigentlich mein Argument: es gibt zu jedem NP-Problem Untermengen für die eine Polynomialzeit-Algorithmus existiert.
Dadurch wird es nicht weniger "Subset-Sum" es ist halt ein Spezialfall.
-
otze schrieb:
Michael E. schrieb:
Ist das Subset-Sum? Immerhin hat man nur sehr wenige verschiedene Münztypen.
naja, ich halte es für eine Instanz von Subset-Sum die polynomiell lösbar ist. Das war ja eigentlich mein Argument: es gibt zu jedem NP-Problem Untermengen für die eine Polynomialzeit-Algorithmus existiert.
Eine einzelne Instanz ist trivialerweise in Polynomialzeit lösbar, weil "Polynomialzeit" sich auf irgendeine Größe bezieht, die wachsen können muss. Aber aus deinem zweiten Satz schließe ich, dass du eigentlich eine Menge von Instanzen meinst, die alle in Polynomialzeit lösbar sind, also anders gesagt eine eingeschränkte Variante des Subset-Sum-Problems.
otze schrieb:
Dadurch wird es nicht weniger "Subset-Sum" es ist halt ein Spezialfall.
Doch, es wird dadurch weniger Subset-Sum. Im üblichen Sprachgebrauch der Literatur meint man mit 3SAT, subset sum, TSP, etc. nur die NP-vollständigen Versionen der entsprechenden Probleme. Es wär sonst etwas zu verwirrend, wenn man das immer dazuschreiben müsste.