Ist es wirklich möglich, Untergrenzen zu beweisen?

Ist es angesichts eines Rechenproblems wirklich möglich, untere Grenzen für eine solche Berechnung zu finden? Ich nehme an, es läuft darauf hinaus, wie ein einzelner Rechenschritt definiert ist und welches Modell wir für den Beweis verwenden, aber beweisen wir dann wirklich eine Untergrenze im Allgemeinen? Was ich damit meine, ist, dass wir beweisen können, dass etwas wie "Problem kann nicht schneller als -Zeit gelöst werden " und nicht "Problem kann in -Zeit oder schneller gelöst werden"? $X$ $t(X)$ $X$ $t(X)$

Ich habe versucht, Informationen speziell zu Untergrenzen und Beweisen von ihnen zu finden, aber ich kann keine wirklich interessanten Empfehlungen zu Büchern / Papieren / Websites zu diesem Thema finden?

complexity-theory time-complexity proof-techniques lower-bounds hsalin
quelle

Antworten:

Wir können solche Dinge absolut beweisen.

Viele Probleme haben triviale Untergrenzen, so dass das Auffinden des Minimums einer Menge von Zahlen (die in keiner Weise sortiert / strukturiert sind) mindestens Zeit benötigt. Der Beweis dafür ist einfach: Ein hypothetischer Algorithmus, der in Zeit abläuft, kann nicht alle Zahlen in der Eingabe untersuchen. Wenn wir also den Algorithmus für eine Eingabe ausführen, können wir feststellen, dass er niemals ein bestimmtes Element der Eingabe untersucht hat. Wenn Sie dieses Element auf ein Minimum reduzieren, kann der Algorithmus fehlschlagen. $n$ $\Omega(n)$ $o(n)$

Eine weniger triviale Untergrenze ist die -Untergrenze für die Sortierung im vergleichsbasierten Modell. Der Beweis dafür lautet wie folgt: Bei einer Eingabe von Zahlen gibt esMögliche Ausgaben (die Eingabe kann eine beliebige Permutation der sortierten Liste sein, die Ausgabe kann also auch eine beliebige Permutation der Eingabe sein). Wenn wir uns darauf beschränken, nur Vergleiche anzustellen, muss unser Algorithmus (im Durchschnitt) mindestens Vergleiche durchführen, umverschiedene Ausgänge. $\Omega(n \log n)$ $n$ $n!$ $\log_2(n!)=\Omega(n \log n)$ $n!$

Untergrenzen können noch stärker sein. Es gibt mehrere Probleme (insbesondere die harten Probleme), für die es eine exponentielle Untergrenze gibt. Zu den Problemen in dieser Klasse gehört die Berechnung optimaler Strategien für Spiele wie (allgemeines) Schach, Dame und Los. Der Beweis hierfür ist über das Zeithierarchietheorem , das (vorbehaltlich einiger Einschränkungen von ) lautet : $EXPTIME$ $f$

Bei gegebener Funktion gibt es ein Rechenproblem, das in der Zeit gelöst werden kann, aber nicht in der Zeit gelöst werden kann . $f$ $O(f(n))$ $o(\frac{f(n)}{\log n})$

Wenn Sie sich also eine Funktion gibt es ein Problem, für dessen Lösung so viel Zeit erforderlich ist. $f$

Schließlich zeigt eine andere Möglichkeit, nicht notwendigerweise eine Zeituntergrenze, sondern etwas noch Stärkeres zu beweisen, die Unentscheidbarkeit eines Problems (z. B. Anhalten, Nachkorrespondenz).

Tom van der Zanden
quelle

Die Größe der Eingabe oder Ausgabe ist die häufigste Untergrenze.

Raphael

$\Omega(n\log n)$ $n$

$O(n\log n)$

L \subseteq N L \subseteq P \subseteq N P \subseteq P S P EIN C E,

$\mathrm{L}\subseteq \mathrm{NL}\subseteq \mathrm{P}\subseteq \mathrm{NP} \subseteq\mathrm{PSPACE}\,,$

L \subset P S P A C E

$\mathrm{L}\subset \mathrm{PSPACE}$

Auf der anderen Seite hat Ryan Williams eine schöne Abhandlung (und einen Vortrag, den ich einige Male gehört habe) mit dem Titel Algorithmen für Schaltkreise und Schaltkreise für Algorithmen , in der er argumentiert, dass das Finden von Untergrenzen und das Finden von Algorithmen nicht grundsätzlich alles sind das anders. Zum Beispiel nennt er den Beweis der Unentscheidbarkeit des Halteproblems als ein Beispiel für einen Algorithmus (die universelle Turing-Maschine), der genau zum Nachweis einer Untergrenze (Unentscheidbarkeit) verwendet wird.

David Richerby
quelle

Ich denke, das ist es, wonach ich gesucht habe: "... du musst irgendwie zeigen, dass kein Algorithmus in einer bestimmten Klasse dein Problem lösen kann." Dies ist der Teil, den ich etwas verwirrend finde, da ich nicht wirklich intuitiv sehen kann, wie man das machen kann so etwas im Allgemeinen zumindest. Wie @Tom van der Zanden beschrieben hat, verstehe ich die minimale Anzahl der Ergebnisse, aber ist dieser Ansatz allgemein? Ich meine allgemein, wie wenn man diese Art von Argument bei der Erstellung der Beweise hat? Danke auch für den Link.

hsalin

@ user1288420 Du bist nicht allein. Wenn jemand intuitiv nachweisen könnte, dass kein Algorithmus in einer bestimmten Klasse ein Problem lösen kann, hätten wir viel mehr Ergebnisse mit niedrigeren Grenzen! In der Regel müssen Sie sich eine Eigenschaft ausdenken, über die jeder Algorithmus in der Klasse verfügt, und nachweisen, dass diese Eigenschaft verhindert, dass ein Problem gelöst wird. Zum Beispiel hat jede Turing-Maschine, die in sublinearer Zeit läuft, die Eigenschaft, dass sie nicht einmal alle Eingaben lesen kann. Das heißt, es kann die meisten Probleme nicht lösen. Das ist trivial. Leider scheinen interessantere Fälle unglaublich schwierig zu sein.

David Richerby

$n$

Es gibt jedoch einen Punkt in der Frage, der weitere Bemerkungen zur Untergrenze (oder zur Komplexitätsgrenze im Allgemeinen) erfordert.

Tatsächlich ist die Wahl eines einzelnen Rechenschritts irrelevant, solange man davon ausgehen kann, dass Rechenschritte eine konstante Obergrenze (und Untergrenze) haben. Das Komplexitätsergebnis ist dasselbe, da es bis zu einer Konstanten definiert ist. Es macht keinen Unterschied, 3 Vergleiche als Einheitsoperationen oder nur eine einzige zu betrachten.

Gleiches gilt für die Datenmenge, die als Referenz für die Bewertung der Berechnungskosten dient. Es macht keinen Unterschied, eine einzelne Ganzzahl oder zwei Ganzzahlen als Einheit für die Größe zu verwenden.

Die beiden Möglichkeiten müssen jedoch zusammenhängen.

$n$ $\log n$ $O(\log n)$

Ob für einen Vorgang Stückkosten in Betracht gezogen werden können, hängt eng mit den Daten zusammen, die als Stückgröße angesehen werden können. Und das hängt davon ab, welche Abstraktionsebene Sie für Ihr Berechnungsmodell auswählen.

babou
quelle

Das Finden aller Vorkommen eines Musters in einer Zeichenfolge erfordert trivialerweise das Lesen der gesamten Zeichenfolge: Wenn das Muster "a" ist, können Sie nicht alle Vorkommen finden, ohne zu prüfen, ob jedes einzelne Zeichen der Zeichenfolge vorhanden ist.

David Richerby

@DavidRicherby Eigentlich nicht immer. Der Boyer-Moore-Algorithmus beginnt am Ende des Musters und springt somit in der Zeichenfolge nach oben. Wenn die versuchte Übereinstimmung fehlschlägt, muss der Anfang der Zeichenfolge nicht gelesen werden. Es verfügt auch über eine ähnliche Optimierung wie der Knuth-Morris-Pratt-Algorithmus, um Versuche zu überspringen, die aufgrund der Struktur des Musters zum Scheitern verurteilt sind. Natürlich gibt es Muster, die das Lesen der gesamten Zeichenfolge erfordern.

Babou

@DavidRicherby Warum hast du gefragt, das wusstest du?

Babou

Ich verstehe deinen zweiten Kommentar nicht. Ihre ursprüngliche Antwort enthielt einen falschen Anspruch. Natürlich wusste ich, dass es falsch war: So konnte ich darauf hinweisen! Andere hätten vielleicht nicht gewusst, dass es falsch ist, und es wäre ihnen verwirrend gewesen, die Antwort so zu belassen, wie sie war.

David Richerby

@DavidRicherby Mein Punkt ist, dass Sie verstanden haben, was ich meinte. Ich hätte vielleicht nicht sagen sollen, als nicht . Dies erforderte keinen Kommentarstil, der die Leser glauben ließ, ich spreche Unsinn. Und während dies zu tun, Sie haben genau den gleichen Fehler sorglos: durch die Angabe „ Finding alle Vorkommen eines Musters in einem String trivialerweise die gesamte Zeichenfolge erfordert das Lesen “, wenn Sie sagten , "haben sollten alle Vorkommen zu finden , eines Musters in einem String kann verlangen den ganzen String lesen ". Ich wollte nur sagen, dass das Lesen der Eingabe nicht immer notwendig ist, um mein vorheriges Beispiel zu mildern.

Babou