Wiki definieren Polynomzeit als Brache:
Ein Algorithmus hat eine Polynomzeit, wenn seine Laufzeit durch einen Polynomausdruck in begrenzt ist die Größe der Eingabe für den Algorithmus, dh $ T (n) = O (n ^ k) $ für eine Konstante $ k $
I. Verstehen Sie, dass im Allgemeinen der Unterschied zwischen Polynomzeit und Exponentialzeit ist, dass die Exponentialfunktion asymptotisch streng schneller wächst als jede Polynomfunktion ( Referenz ).
Ich versuche, den Kern zu verstehen Definition von Exponentialzeit .
- Welche Elemente bewirken, dass ein Algorithmus in Exponentialzeit ?
- Welche Änderung muss ich am -Polynomausdruck vornehmen? Exponentialzeit ? (Mit it beziehe ich mich am Anfang auf die Algorithmusdefinition der Frage)
Kommentare
- 1. Mach exponentiell viele Dinge. 2. Verwenden Sie das Polynom als Potenz einer Basis > 1.
- Ich verstehe ' Ihre Sekunde nicht Frage. Polynome sind Polynome; Exponentiale sind Exponentiale. Zu fragen, was Sie ändern müssen, um ein Polynom in ein Exponential zu verwandeln, ist wie zu fragen, was Sie ändern müssen, um einen Logarithmus in einen Kosinus zu verwandeln.
- @DavidRicherby Gibt es exponentielle Zeitfunktionen, wenn P = NP? Wie können Sie eine exponentielle Zeitfunktion in Bezug auf den Polynomausdruck definieren?
- Exponentialfunktionen werden sicherlich noch existieren, wenn P = NP. Es gibt wahrscheinlich immer noch Probleme, bei denen ' exponentielle Zeit benötigt, selbst wenn P = NP, obwohl keine sofort in den Sinn kommt. Eine Exponentialfunktion kann als Polynom definiert werden, aber dieses Polynom muss unendlich lang sein. Sie können Taylor Expansions nachschlagen, wenn Sie ' daran interessiert sind.
- @ymbirtt Selbst die einfachste Version des Zeithierarchiesatzes besagt, dass es für kein EXPTIME-vollständiges Problem einen Polynom-Zeit-Algorithmus gibt. Das ' ist ein bedingungsloses Ergebnis: ' hängt nicht von der Annahme ab, dass P $ \ neq $ NP.
Antwort
-
Für diese Frage gibt es keine einfache Antwort, obwohl es Anzeichen gibt, auf die man achten muss Das Untersuchen jeder möglichen Teilmenge einer Menge ist beispielsweise exponentiell. Wenn ich also eine Menge von ganzen Zahlen $ \ {x_1, …, x_n \} $ hätte und jede Teilmenge dieser Mengen überprüfen wollte, um festzustellen, ob sie sich summieren bis $ 0 $ müsste ich genau $ 2 ^ n $ Teilmengen berücksichtigen, was diese Methode zu einer exponentiellen Zeit macht. Mehrere verschiedene Fallen können jedoch zu einer exponentiellen Zeit für einen Algorithmus führen. Analysieren Sie Algorithmen daher von Fall zu Fall, anstatt nach breiten Kategorien Ausschau zu halten.
-
Wenn ein Algorithmus $ n ^ 2 $ Schritte benötigt, um abgeschlossen zu werden, ist er ein Polynom. Wenn er $ 2 ^ n $ Schritte benötigt, ist er exponentiell. Der Unterschied ist die Position des $ n $. Wenn etwas $ O (n ^ m) $ für $ n > 1 $ ist, $ m > 0 $, dann ist es „s Polynom in $ n $ für festes $ m $, aber exponentiell in $ m $ für festes $ n $.
Kommentare
- Vorsicht. Die Funktion $ n ^ m $ ist kein ' t-Polynom in $ n $, es sei denn, $ m $ ist eine Konstante. Und wenn $ m $ ist eine Konstante, ' Es macht keinen Sinn zu sagen, dass die Funktion in dieser Konstante exponentiell ist.
- Ja, Sie ' ist richtig. Ich ' werde das klarstellen.
Antwort
Wenn Sie ein Problem betrachten und dessen gesamten Suchraum aufzählen, erhalten Sie häufig einen Brute-Force-Algorithmus mit exponentieller Zeit. In der Regel denken Sie an Teilmengenprobleme (in SAT würden Sie eine Teilmenge von auswählen Variablen auf true gesetzt), Permutationsprobleme (in TSP ist jede Tour eine Permutation der Städte) und Partitionsprobleme (in der Grafikfarbe versuchen Sie p die Eckpunkte in Farbklassen einteilen). Oder sortieren Sie sogar: Es gibt $ n! $ Permutationen von $ n $ ganzen Zahlen. Gehen Sie jede Permutation durch und prüfen Sie, ob sie sortiert ist. Dumm (und langsam), aber es funktioniert.
Kommentare
- Beachten Sie jedoch, dass $ O (n!) $ Noch schlimmer ist als $ O ( k ^ n) $. Wenn Sie ' immer noch versuchen, etwas über die Zeitkomplexität zu lernen, kann dies eine nützliche Sache sein, die Sie sich selbst beweisen können.