Computational Complexity Theory ist komplex. Mein Verständnis der Polynomzeit bezieht sich auf andere Zeitkomplexitätsklassen wie die nicht deterministische Polynomzeit. Dies ist in Ordnung für Ingenieure und Mathematiker, aber ich suche nach einer einfachen Definition des Begriffs, die für Laien geeignet ist.
- Wäre es falsch, die Polynomzeit als "in (Rechen-) Operationen gemessene Zeit " umzuwandeln?
Natürlich würde es nachfolgende Qualifikationen für verschiedene Zeitkomplexitätsklassen geben, und die Zeitkomplexität könnte ein Verhältnis sein, das auf der Problemgröße basiert, aber auch dies ist etwas komplexer als das, wonach ich hier suche.
Antworten:
"Polynomzeit" ist eine Aussage über die Laufzeit eines Algorithmus. Theoretisch ist die Laufzeit eines Algorithmus eine Zählung der Anzahl der Grundoperationen, die er ausführt. Dies wird voraussichtlich proportional zu der Zeit sein, die der Algorithmus benötigt, um auf einem Computer ausgeführt zu werden. Polynomzeit bedeutet, dass die Laufzeit höchstens ein (nicht spezifiziertes) Polynom in der Größe der Eingabe ist; zB proportional zum Quadrat der Eingabegröße oder des Würfels oder so ähnlich. Polynomzeitalgorithmen sind häufig effizient genug, um in der Praxis implementiert zu werden.
Siehe https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time und https://en.wikipedia.org/wiki/Cobham%27s_thesis .
quelle
Polynomzeitalgorithmen sind Algorithmen, deren Laufzeit sich um einen konstanten Faktor erhöht, wenn die Größe der Eingabe verdoppelt wird.
Exponentielle Zeitalgorithmen sind Algorithmen, deren Laufzeit sich um einen konstanten Faktor erhöht, wenn sich die Eingabegröße um 1 erhöht.
Für Laien können Sie möglicherweise NP-vollständige Probleme mit Problemen identifizieren, die nur in exponentieller Zeit lösbar sind, obwohl dies, wie wir wissen, in vielerlei Hinsicht falsch ist.
quelle
Ja. Völlig falsch.
"Zeit" bedeutet zwar "in (Rechen-) Operationen gemessene Zeit", aber Sie haben "Polynom" überhaupt nicht übersetzt. Es ist, als würde man "zwölf Tage" als "Zeit, gemessen in der Anzahl der Umdrehungen der Erde um ihre Achse" übersetzen. Genau das bedeutet "Tag", aber was ist mit "zwölf" passiert?
Polynome sind von Natur aus mathematische Objekte, und ich bezweifle, dass es eine Möglichkeit gibt, sie ohne Verwendung von Mathematik zu erklären. Sie können erklären, dass Polynomalgorithmen normalerweise als einigermaßen effizient angesehen werden, aber das ist eine Konsequenz dessen, was eine Polynombeziehung ist, keine Erklärung dafür.
quelle
Es gibt wirklich nicht viel, was Sie tun können, um einfache Definitionen dieser Problembereiche bereitzustellen. Denken Sie daran, dass Problemräume wie P und NP durch asymptotisches Verhalten definiert werden, wenn eine bestimmte Zahl
nins Unendliche geht. Es gibt keine Laiensituationen, in denen es nützlich ist, ins Unendliche zu gehen, und die Präzision, die erforderlich ist, um es so zu definieren, ist brutal.Als solches finde ich es am einfachsten, P und NP als "schnell" und "langsam" zu beschreiben und dann das praktische Beispiel der Kryptographie zu verwenden, weil es für Menschen interessant ist. Ich beginne mit NP (weil es schnelle und langsame P-Algorithmen gibt, möchte ich ihr Konzept von "langsam" mit dem der exponentiellen Zeit verankern, bevor ich P einbringe). Jeder hat sich irgendwo mit einer Art geometrischem Wachstum befasst, auch wenn es nur Zinseszins ist, also gibt es etwas, von dem man ausgehen kann.
Sobald ich denke, dass sie eine Vorstellung von der exponentiellen Zeit haben, stelle ich den Kryptographie-Link vor. Eines der Ziele der Kryptographie ist, dass das Hinzufügen von 1 Bit zu einem Schlüssel die Zeit verdoppelt, die jemand benötigt, um ihn zu brechen. Der wesentliche Teil besteht darin, die Idee zu verbinden, dass das Hinzufügen von Arbeit zum Sender / Empfänger den Arbeitsaufwand des Angreifers vervielfacht.
Damit kann ich dann Moores Gesetz ansprechen, das sehr grob besagt, dass sich die Rechenleistung alle 18 Monate verdoppelt. Das bedeutet, dass mein Angreifer doppelt so viel Arbeit leisten kann, wenn er darauf warten kann, dass die Hardware aufholt. Wenn sich seine Angriffsfähigkeit verdoppelt, muss ich etwas hinzufügen. Dann verdoppelt er sich wieder und ich füge ein bisschen hinzu. Dann kann ich zeigen, wie asymmetrisch ist dieses Spiel - jedes Mal , wenn sie eine tun massive Menge an zusätzlicher Arbeit, sie hat gerade eine wenig zusätzliche Arbeit zu tun habe , Dinge zu halten , auch.
Jetzt kann ich Polynomzeit als Algorithmen lehren, die schneller als die Exponentialzeit laufen. Dies ist eine kleine Vereinfachung, aber für einen Laien denke ich, dass es in Ordnung ist. Wenn mein Krypto-Algorithmus eine Polynomzeit wäre und die Rechengeschwindigkeit meines Angreifers besser würde, müsste ich immer schneller Bits hinzufügen und das System blockieren. Jeder weiß, was es bedeutet, wenn ein Computer langsam läuft!
quelle