Algorithmus transformieren ...
-
In welchen Fällen, kann man einen Algorithmus mit exponentiellem Aufwand, in einen mit besserem Aufwand ( zB linearem ) transformieren ? Bei der Berechnung des n-ten Fibonacci-Gliedes gelingt das.
-
Das kann man so nicht beantworten. Man glaubt heute, dass es Probleme gibt, wie z.B. die Primzahlfaktorisierung, die man nicht effizient (das heisst nur in exponentieller Zeit) lösen kann.
Allerdings konnte bisher noch keiner beweisen, dass es keinen effizienten Algorithmus dafür gibt.
Meinst du bei Fibonacci den Rechenunterschied zwischen der rekursiven und der iterativen Formel?
-
icarus2 schrieb:
Das kann man so nicht beantworten. Man glaubt heute, dass es Probleme gibt, wie z.B. die Primzahlfaktorisierung, die man nicht effizient (das heisst nur in exponentieller Zeit) lösen kann.
Allerdings konnte bisher noch keiner beweisen, dass es keinen effizienten Algorithmus dafür gibt.
Für die Primzahlzerlegung gibt es bereits einen Algorithmus, der auf Quantencomputern in Polynomialzeit arbeitet. Insofern ist Primzahlzerlegung schonmal (dem Anschein nach) nicht ganz so schwer wie andere Probleme. Deswegen wird auch vermutet, dass Primzahlzerlegung nicht NP-vollständig ist. Für NP-vollständige Probleme gibt es dagegen bisher keinen Quantenalgorithmus (und auch keinen klassischen Algorithmus), der in Polynomialzeit arbeitet. Es ist aber noch offen, ob die NP-vollständigen Probleme wirklich nicht in Polynomialzeit lösbar sind.
Es ist aber bekannt, dass P != EXP, wobei P die Klasse der Probleme ist, die in Polynomialzeit lösbar sind, und EXP die Klasse der Probleme, die in Exponentialzeit lösbar sind, jeweils auf deterministischen Turingmaschinen. Das heißt, dass es tatsächlich Probleme gibt, für die ein Exponentialzeit-Algorithmus existiert, aber kein Polynomialzeit-Algorithmus, egal wieviel Speicher man auch verwenden darf.
icarus2 schrieb:
Meinst du bei Fibonacci den Rechenunterschied zwischen der rekursiven und der iterativen Formel?
Ob iterativ oder rekursiv ist komplexitätstheoretisch völlig irrelevant. Was relevant ist, ist die Arbeit, die der Algorithmus ausführt. Wenn der rekursive Algorithmus ein vielfaches der Arbeit des iterativen Algorithmus ausführt, ist der rekursive langsamer. Das liegt aber in keinster Weise daran, dass er rekursiv ist, sondern einfach daran, dass er etwas anderes macht.
-
Christoph schrieb:
Für die Primzahlzerlegung gibt es bereits einen Algorithmus, der auf Quantencomputern in Polynomialzeit arbeitet.
Jap, allerdings gibt es im Moment noch keine Quantencomputer. Ich habe von elektronischen Rechnern gesprochen (was ich vielleicht hätte sagen sollen ^^).
Christoph schrieb:
Es ist aber bekannt, dass P != EXP
Bist du dir sicher? Ich dachte immer, man hätte das noch nicht sauber beweisen können?
Christoph schrieb:
Ob iterativ oder rekursiv ist komplexitätstheoretisch völlig irrelevant. Was relevant ist, ist die Arbeit, die der Algorithmus ausführt. Wenn der rekursive Algorithmus ein vielfaches der Arbeit des iterativen Algorithmus ausführt, ist der rekursive langsamer. Das liegt aber in keinster Weise daran, dass er rekursiv ist, sondern einfach daran, dass er etwas anderes macht.
Ist klar, dass Rekursion nicht zwingend mehr Aufwand bedeutet. Ich habe mich auf den Fibonacci Fall bezogen.
-
P != EXP
Wo ist denn der Unterschied zu P != NP? Und wenn es keinen gibt, woher nimmst du dann die Gewissheit?
-
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.
-
knivil schrieb:
P != EXP
Wo ist denn der Unterschied zu P != NP? Und wenn es keinen gibt, woher nimmst du dann die Gewissheit?
NP und EXP sind zwei vollkommen unterschiedlich definierte Klassen von Problemen.
NP enthält die Entscheidungs-Probleme, für deren Ja-Antworten Zertifikate existieren, die in Polynomialzeit verifizierbar sind.
EXP enthält die Entscheidungs-Probleme, die in Exponentialzeit entscheidbar sind.
(Jeweils auf deterministischen Turingmaschinen). Die Definition von NP enthält also an keiner Stelle "exponentielle Zeit", sondern nur "Ja-Antwort ist in Polynomialzeit verifizierbar".
Jetzt ist es aber so, dass bei NP-Problemen die Zertifikate für Ja-Antworten polynomielle Länge nicht überschreiten dürfen (sonst könnte man sie nicht in Polytime verifizieren). Deswegen kann man, wenn man exponentielle Laufzeit zur Verfügung hat, einfach alle potentiellen Ja-Zertifikate eins nach dem anderen durchprobieren: Findet man ein gültiges, ist die Antwort "ja", findet man keins, ist die Antwort "nein". Das zeigt, dass jedes NP-Problem in EXP liegt.
Andersrum ist es aber viel unklarer: Nur weil ein Problem in Exponentialzeit lösbar ist, heißt das noch lange nicht, dass man ein Zertifikat konstruieren kann, das die Ja-Antwort bestätigt und das in Polynomialzeit verifizierbar ist.
Die Idee bei NP kann man auch so sehen: Angenommen ich würde behaupten, dass ich ein NP-vollständiges Problem effizient lösen könnte, zum Beispiel 3SAT. Jetzt möchte ich aber den Algorithmus nicht bekanntgeben. Für jede 3SAT-Instanz, d.h. aussagenlogische Formel, die du mir schickst, kann ich dir aber schnell beantworten, ob die erfüllbar ist oder nicht. Aber warum solltest du mir glauben, dass meine Antworten korrekt sind? Du kannst die Erfüllbarkeit ja selber nicht ausrechnen, weil das viel zu kompliziert ist. Bei einem EXP-Problem müsstest du mir das auch einfach glauben, dort hätte ich (falls NP != EXP) keine Möglichkeit dir zu beweisen, dass meine Antworten korrekt sind.
Bei NP sieht es anders aus: Bei jedem NP-Problem muss für mich eine Möglichkeit existieren, dir ein Zertifikat zu geben, falls die Antwort "ja" ist. Dieses Zertifikat kannst du in Polynomialzeit prüfen, um dich davon zu überzeugen, dass meine Ja-Antwort korrekt ist. Die Existenz solcher Zertifikate ist dadurch sichergestellt, dass ein Problem in NP liegt.
Für Nein-Antworten gibt NP allerdings keine Zertifikate, daher kommt eine gewisse Asymmetrie ins Spiel. Das natürliche Gegenstück zu NP ist CoNP: Dort gibt es nur für Nein- statt für Ja-Antworten Zertifikate. Ob NP = CoNP gilt, ist eine offene Frage.
-
Das geht auch oft bei der Verwendung von Par-parametrisiertern Algorithmen.
Beispiel: Vertex-Cover
gegeben: Geraph G = (V,E)
Ziel Teilmenge der Knoten finden, die alle Kanten andecken.
Entscheidungsproblem:
Gibt es für einen gegebenen Graphen ein Vertex-Cover der Größe <= k?
(k-Vertex-Cover)Algorithmus von Buss und Goldsmith:
1. Bestimme Menge H alle Knoten mit Grad größer k
(Diese müssen auf jeden fall im Cover sein, weil es für solche Knoten nicht möglich ist, alle inzidenten Knoten aufzunehmen)
2. Ist |H| > k Ausgabe "Nein"
3.Nimm H ins Vertex Cover auf
4. Berechne G' = G - H (Also den Graph ohne die Knoten und kanten die durch die menge H schon abgedeckt sind)
5. Berechne m = k - |H| (Die Anzahl der Knoten die noch zusätzlich in ein gültiges k Cover aufgenommen werden können.
6. Falls G' mehr als km Knoten besitzt gib "Nein" aus.
( Man kann noch höchstens m knoten aufnehmen. Jeder Knoten hat hächstens Grad k, also können maximal noch km kanten abgedeckt werden)
7.Löse das Restproblem durch auflistung aller möglichen Teilmengen aus denen die restlichen aufnehmbaren Knoten bestehen können.laufzeiten:
1. O(kn) (Adjazensliste durchlaufen jeweils bis maximal Knoten k)
2. konstant
3. konstant
4. O(kn)
5.konstant
6.konstant
7. Es gibt noch höchstnes k*m kanten. Also 2*kn Knoten.
Aufzählen aller m elementigen Teilmengen: O((2*k*m)^ m) <= O((2k) ^2k)
Test einer solchen teilmenge in O(k*m)
Zusammen: O(2k*k2*k * k^2)Also ist die Laufzeit unabhängig von der Knoten und Kantenanzahl des Graphen!!!
Für konstante und kleine k (Das k des k Covers) eine Polynomialzeitalgorithmus!
-
OK, also nicht für jede Instanz des ursprünglichen Problems...
Aber wenn man Glück hat hat man gerade eine Instanz bei der eben doch ein Polynomialzeitalgorithmus existieren kann.
-
Und der Annaghme das P != NP gilt. Sonst kann man sich den Aufwand nach Par-parametrisiertern Algorithmen zu suchen eh sparen.
-
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.