Gibt es Probleme, für die Divide-and-Conquer / Rekursion nachweislich nutzlos ist?

Wenn wir versuchen, einen Algorithmus für ein neues Problem zu konstruieren, ist das Teilen und Erobern (unter Verwendung von Rekursion) einer der ersten Ansätze, die wir versuchen. In einigen Fällen scheint dieser Ansatz jedoch erfolglos zu sein, da das Problem mit zunehmendem Input viel komplizierter wird.

Meine Frage ist: Gibt es Probleme, für die wir beweisen können, dass ein Divide-and-Conquer-Ansatz nicht zur Lösung beitragen kann? In den folgenden Zeilen versuche ich, dies formeller zu gestalten.

Sei ein bestimmtes Problem, dessen Eingabe die Größe (z. B. ein Problem, das eine Eingabe eines Arrays von Zahlen akzeptiert ). Angenommen, wir haben einen rekursiven Algorithmus zum Lösen von . Die rekursive Laufzeit dieses Algorithmus wird unter der Annahme eines Orakels berechnet, das für jedes in konstanter Zeit lösen kann . Zum Beispiel: $P(n)$ $n$ $n$ $P(n)$ $P(k)$ $k<n$

Die rekursive Laufzeit der binären Suche ist , da nur ein Vergleich und zwei rekursive Aufrufe verwendet werden. $O(1)$
Das maximale Element in einem Array kann in der rekursiven Zeit . $O(1)$
Die rekursive Laufzeit der Zusammenführungssortierung ist aufgrund des Zusammenführungsschritts . $O(n)$

Die rekursive Zeit ist normalerweise kleiner als die tatsächliche Laufzeit, was die Tatsache widerspiegelt, dass der rekursive Algorithmus einfacher ist als eine einfache nicht rekursive Lösung für dasselbe Problem.

Jetzt ist meine Frage:

Gibt es ein Problem, das in der Zeit gelöst werden kann , aber nachweislich keinen rekursiven Algorithmus mit einer rekursiven Laufzeit hat, die asymptotisch kleiner als ? $f(n)$ $f(n)$

Einige spezifische Varianten dieser Frage sind:

Gibt es ein Problem in das keinen Algorithmus mit rekursiver Laufzeit ? (Vielleicht sortieren?) $P$ $O(1)$
Gibt es ein Problem mit einem Exponentialalgorithmus, der keinen Algorithmus mit polynomialer rekursiver Laufzeit hat?

EDIT: Entgegen meiner Vermutung hat die Sortierung einen Algorithmus mit rekursiver Laufzeit $O(1)$ . Es ist also noch offen, ob es in ein Problem gibt, das keinen Algorithmus mit rekursiver Laufzeit . $P$ $O(1)$

cc.complexity-theory recursion Erel Segal-Halevi
quelle

Vielleicht würde der Nachweis einer Kernelisierungsuntergrenze den Trick tun en.wikipedia.org/wiki/Kernelization

Tyson Williams

Die Ausgabegröße ist eine Untergrenze für die Laufzeit. Daher hat jedes Problem mit der Ausgabegröße, die ihrer Komplexität entspricht, diese Eigenschaft.

Chao Xu

@Chao Xu: Warum trifft Ihr Argument nicht auf die Eingabegröße zu? Ich denke, dass das Argument davon abhängt, welches Kostenmodell (und Rechenmodell) wir betrachten.

Tsuyoshi Ito

Dies ist das Gegenteil von dem, wonach Sie suchen, aber angesichts dieser Orakel kann Ihr Modell die Teilmengen-Summe - ein bekanntes NP-Complete-Problem - in linearer Zeit lösen, sodass P! = NP in diesem Fall viel leistungsfähiger ist als iterative Funktionen . Die Funktion würde einfach prüfen, ob die aktuelle Menge zu 0 addiert, und sich dann, wenn nicht, auf die n Teilmengen der Größe n-1 aufruft. Die Laufzeit selbst ist n! Das ist jedoch schlimmer als Brute Force, daher bin ich mir nicht sicher, wie viel Wert dieses Modell bietet, aber es ist immer noch eine interessante Frage.

Phylliida

Ihre letzte Bearbeitung ("rekursiv" -> "Teilen und Erobern") ist eine ziemlich große Änderung der Frage. Ich würde stattdessen einfach eine separate Frage stellen. Wir können wahrscheinlich Dinge über Teilen und Erobern sagen, indem wir zum Beispiel die Tiefen von Schaltkreisen betrachten.

Usul

Antworten:

Gibt es ein Problem mit einem Exponentialalgorithmus, der keinen Algorithmus mit polynomialer rekursiver Laufzeit hat?

Ja. Beachten Sie, dass eine Tally-Sprache, wenn sie einen „rekursiven Algorithmus“ mit einem Polynom „rekursive Laufzeit“ hat, in P ist. In E ∖ P gibt es eine Tally-Sprache durch ein Standarddiagonalisierungsargument.

Gibt es ein Problem, das in der Zeit gelöst werden kann , aber nachweislich keinen rekursiven Algorithmus mit rekursiver Laufzeit ? $f(n)$ $o(f(n))$

Es mag vom Rechenmodell abhängen, aber ich bezweifle, dass dies bekannt ist, da der Zeithierarchiesatz für Turing-Maschinen mit zwei Bändern nicht leistungsfähig genug ist, um beispielsweise O ( n ² ) -Zeit und o ( n ² ) -Zeit sogar zu unterscheiden ohne letzterem den zeitlich konstanten Zugriff auf die Antworten in kleineren Instanzen zu gewähren.

Zufällige Kommentare zu Ihren Fragen in diesem Beitrag:

Ich glaube nicht, dass diese Fragen mit der Nützlichkeit rekursiver Programme zusammenhängen, ungeachtet dessen, was der Titel des Beitrags und Ihre Wahl der Terminologie nahelegen. Wie der BVMR in einer Antwort schrieb, sind Rekursionen und Iterationen in gewissem Sinne gleichwertig. Stattdessen denke ich, dass die Fragen einen Zusammenhang mit der Nützlichkeit des Divide-and-Conquer-Ansatzes haben.
In der Komplexitätstheorie wird ein verwandter Begriff zu Ihrem Begriff von "rekursiven Algorithmen" mit ihrer "rekursiven Laufzeit" als "längenverringernde Selbstreduktionen" mit ihrer zeitlichen Komplexität bezeichnet.
Ein Teil Ihrer Fragen (definitiv der Teil, der sich auf sublineare Zeitalgorithmen bezieht) hängt von der Wahl des Rechenmodells ab.

Tsuyoshi Ito
quelle

Zu Ihrer ersten Antwort: Lassen Sie mich versuchen, sie zu erweitern, um festzustellen, ob ich sie richtig verstehe. Angenommen, eine bestimmte Tally-Sprache verfügt über einen Algorithmus mit dem Polynom "rekursive Laufzeit". Ein Polynomalgorithmus für diese Sprache kann unter Verwendung dynamischer Programmierung konstruiert werden. Die Antwort für

kann in Polynomzeit gefunden werden, da keine rekursiven Aufrufe erforderlich sind. Die Antwort für

kann dann in Polynomzeit unter Verwendung der Antwort für

. Dann kann die Antwort für

in Polynomzeit unter Verwendung der Antworten für

und

n = 0

$n=0$

n = 1

$n=1$

n = 0

$n=0$

n = 2

$n=2$

n = 1

$n=1$

n = 0

$n=0$ usw. Ist das richtig?

Erel Segal-Halevi

Ja, obwohl es besser ist, asymptotische Begriffe wie „Polynomzeit“ zu vermeiden, wenn Sie über einen bestimmten Wert von n sprechen. Zum Beispiel ist es nicht sinnvoll zu sagen, dass der Algorithmus in Polynomzeit läuft, wenn n = 0 ist. Wenn eine Tally-Sprache einen „rekursiven Algorithmus“ mit polynomieller „rekursiver Laufzeit“ p (n) hat, können wir die Antwort für n ohne das Orakel berechnen, indem wir die Antworten für 0, 1, 2,…, n berechnen, und dies dauert Zeit

, die in n polynomisch ist.

O (\sum_{i = 0}^{n} p (i))

$O(\sum_{i=0}^n p(i))$

Tsuyoshi Ito

Vielen Dank. Ich stimme Ihrem Kommentar zu Divide-and-Conquer zu und habe die Frage entsprechend bearbeitet.

Erel Segal-Halevi

Jede Frage, die eine rekursive Antwort hat, hat eine iterative Antwort und umgekehrt.

Jeder rekursive Algorithmus kann iterativ umgeschrieben werden und umgekehrt.

Daher steht Ihre Frage nicht gut.

BVMR
quelle

Die Komplexität eines Algorithmus, wie ich ihn in der Frage definiert habe, bleibt im Allgemeinen nicht gleich, wenn er von iterativ in rekursiv konvertiert wird. Zum Beispiel kann das Maximum von n Elementen durch einen iterativen Algorithmus mit O (n) -Operationen gefunden werden, aber es kann auch durch einen rekursiven Algorithmus mit O (1) -Operationen gefunden werden (von denen einer ein rekursiver Aufruf ist). Obwohl letztendlich die Laufzeit beider Algorithmen gleich ist, ist der rekursive Algorithmus einfacher zu programmieren, da er weniger Operationen hat.

Erel Segal-Halevi

-2

Ich bin mir nicht sicher, ob ich Ihren Begriff "rekursive Komplexität" richtig verstehe.

$f$

f (0, \vec{x}) = c (\vec{x}) f (n + 1, \vec{x}) = g (f (n, \vec{x}), n, \vec{x})

$f(0,\vec x) = c(\vec x)\\ f(n+1,\vec x) = g(f(n,\vec x),n,\vec x)$

$c$ $g$ $\mathcal{O}(1)$ $\mathcal{O}(1)$

Wenn alle meine Annahmen erfüllt sind, kann das gesuchte Beispiel nicht primitiv rekursiv sein.

DFF
quelle

Bitte erläutern Sie die Abstimmungen

DFF

P (k)

$P(k)$

k < n

$k<n$

g (f (n, x), n, x)

$g(f(n,x),n,x)$

f (n, x)

$f(n,x)$ das hat konstante Laufzeit. Ich habe Sie nicht abgelehnt, aber dies ist eine einjährige beantwortete Frage, und Sie haben auch eine bestimmte Definition falsch interpretiert.

Chazisop

g

$g$

O (1)

$\mathcal{O}(1)$

f (n, x)

$f(n,x)$

O (1 \circ 1) = O (1)

$\mathcal{O}(1\circ 1)=\mathcal{O}(1)$

g

$g$

O (1)

$O(1)$

ahh, ok ... jetzt macht alles Sinn ... danke für die Klarstellung ... Ich war wahrscheinlich verwirrt darüber, dass rekursive Komplexität nicht rekursiv aufgerufen wird ^^ (was aus der Definition imo nicht sehr klar ist)

DFF