Gibt es ein nichttriviales Problem in der Theorie der seriellen Algorithmen mit einer nichttrivialen Polynomuntergrenze von

In der Theorie der verteilten Algorithmen gibt es Probleme mit Untergrenzen wie $\Omega(n^2)$ , die "groß" (ich meine größer als ) und nicht trivial sind. Ich frage mich, ob es Probleme mit ähnlichen Grenzen in der Theorie des seriellen Algorithmus gibt. Ich meine, die Ordnung ist viel größer als .$\Omega(n\log n)$$\Omega(n\log n)$

Mit trivial meine ich "erhalten, nur wenn man bedenkt, dass wir die gesamte Eingabe lesen müssen" und ähnlich.

Es gibt solche Probleme nach dem Zeithierarchiesatz. Nehmen Sie einfach jedes Problem, das für eine große Komplexitätsklasse vollständig ist. Nehmen Sie zum Beispiel ein Problem, das für $\mathsf{ExpTime}$ vollständig ist . Ein solches Problem wird sein , für alle c ∈ N .$\Omega(n^c)$$c\in\mathbb{N}$

Beachten Sie jedoch auch, dass es für Probleme in keine starken Zeituntergrenzen im Mehrband-TM-Modell gibt und die Existenz linearer Zeitalgorithmen für SAT mit dem aktuellen Wissensstand übereinstimmt. (Im Single-Tape-TM-Modell ist es nicht schwierig zu zeigen, dass viele Probleme wie Palindrome Ω ( n 2 ) -Zeit erfordern, aber solche Untergrenzen hängen im Wesentlichen von den Einzelheiten des Single-Tape-TM-Modells ab.)$\mathsf{NP}$$\Omega(n^2)$

Einige einfache Probleme, deren Untergrenzen größer als die Größe ihrer Eingaben sind, sind Algorithmen, deren Ausgabegrößen größer als ihre Eingabegrößen sind.

Einige Beispiele:

• Das Problem der Auflistung aller Lösungen für 3-SAT oder ähnlich das Problem der Auflistung aller Hamilton-Zyklen . Diese Probleme haben im schlimmsten Fall eine exponentielle Anzahl von Lösungen. Sie haben also eine Untergrenze von . Interessanterweise hat das 3-SAT-Problem selbst keine bekannten superlinearen (größer als Ω ( n ) ) Grenzen! Das heißt, wir wissen nicht, ob es schwieriger als linear ist!$\Omega (c^n),c>1$$\Omega (n)$
• Sie können sogar neue Algorithmen wie diesen erstellen: "Vervollständigen eines Graphen", dh , wobei E = ∅ und n = | V | Der Algorithmus gibt einen Graphen G ' = V , E ' aus , wobei E ' = { u , v | u ≠ v ∧ u , v ∈ V } .$G = V,E$$E=\varnothing$$n=|V|$$G' = V,E'$$E'=\left\{u,v|u\neq v\space\wedge\space u,v\in V \right\}$

Darüber hinaus können Sie möglicherweise ein Problem mit Ausgängen in der Größe von zusammenstellen, wobei ein Problem darin besteht, dass Ω ( n 2 ) als Eingang verwendet wird und Ausgänge in der Größe von Ω ( n ) oder sogar Ω ( 1 ) ausgegeben werden ( beispielsweise , dass etwas zählt die Anzahl Ausgänge) , ein Problem zu erhalten, nimmt Ω ( n ) -sized Eingabe und gibt Ω ( n ) -sized Ausgang, und doch hat eine Laufzeit von mehr als Ω ( n $\Omega (n^2)$$\Omega (n^2)$$\Omega (n)$$\Omega (1)$$\Omega(n)$$\Omega (n)$$\Omega (n)$. Es kann jedoch sehr schwierig sein zu beweisen (dass es keine Abkürzung gibt, um die Antwort in kürzerer Zeit zu erhalten).

Eine andere Möglichkeit, wie einige Probleme Untergrenzen kennen, besteht darin, das Berechnungsmodell einzuschränken.

Obwohl die Untergrenze der Vergleichssorte nicht überschreitet , denke ich, dass es sich lohnt, darüber zu diskutieren. Die Vergleichssortierung ist auch ein Problem, das eine größere Untergrenze als die Eingangsgröße aufweist, deren Untergrenze jedoch Ω ( n log n ) und in nicht überschreitet . Als ich dies untersuchte, fand ich jedoch diese Frage zum Mathoverflow: Superlineare Zeitkomplexitätsuntergrenzen für jedes natürliche Problem in NP . Weitere in der Antwort aufgeführte Beispiele liegen weit unter Ω ( n log n $\Omega (n\log n)$$\Omega (n\log n)$$\Omega (n\log n)$. Ich denke, das Wesentliche ist, wenn Sie das Berechnungsmodell einschränken, können Sie Untergrenzen für Probleme erhalten, für die wir sie sonst nicht haben. Und wenn Sie das Berechnungsmodell nicht einschränken, ist es sehr schwierig, Untergrenzen für Probleme zu beweisen.