Gibt es für jede berechenbare Funktion

19

Für jede berechenbare Funktion gibt es ein Problem, das bestenfalls in Zeit gelöst werden kann, oder gibt es eine berechenbare Funktion so dass jedes Problem, das in gelöst werden kann, gelöst werden kann auch in Zeit gelöst werden? $f$ $\Theta(f(n))$ $f$ $O(f(n))$ $o(f(n))$

Diese Frage tauchte gestern in meinem Kopf auf. Ich habe jetzt ein bisschen darüber nachgedacht, kann es aber nicht herausfinden. Ich weiß nicht wirklich, wie ich das googeln soll, also frage ich hier. Folgendes habe ich mir ausgedacht:

Mein erster Gedanke war, dass die Antwort ja lautet: Für jede berechenbare Funktion das Problem "Ausgabe von Punkten" (oder Erstellen einer Zeichenfolge mit Punkten oder was auch immer) offensichtlich nicht in ) gelöst werden Zeit. Wir müssen also nur zeigen, dass es in Zeit gelöst werden kann . Kein Problem, nimm einfach den folgenden Pseudocode: $f$ $f(n)$ $f(n)$ $o(f(n))$ $O(f(n))$

x = f(n)
for i from 1 to x:
    output(".")

Dieser Algorithmus löst eindeutig das angegebene Problem. Und es ist Laufzeit ist offensichtlich in , also Problem gelöst. Das war einfach, oder? Außer nein, das liegt nicht daran, dass Sie die Kosten für die erste Zeile berücksichtigen müssen. Die Laufzeit des obigen Algorithmus liegt nur in wenn die zur Berechnung von erforderliche Zeit in . Dies gilt natürlich nicht für alle Funktionen ¹ . $\Theta(f(n))$ $\Theta(f(n))$ $f(n)$ $O(f(n))$

Dieser Ansatz brachte mich also nicht weiter. Ich wäre dankbar, wenn jemand mich in die richtige Richtung weisen würde, um dies richtig herauszufinden.

¹ Betrachten Sie zum Beispiel die Funktion $p(n) = \cases{1 & \text{if $n$ is prime} \\ 2 & \text{otherwise}}$ . Es ist klar, dass $O(p(n)) = O(1)$ , aber es gibt keinen Algorithmus, der $p$ in berechnet $O(1)$ .

complexity-theory sepp2k
quelle

1

Ich denke nicht, dass Ihre beiden Aussagen in Ihren ersten Absätzen unbedingt gegensätzlich sind: Was ist, wenn Sie ein , bei dem es ein Problem gibt, das in gelöst werden kann , nicht in , noch in Zeit?

f

$f$

O (f (n))

$O(f(n))$

o (f (n))

$o(f(n))$

Θ (f (n))

$\Theta(f(n))$

Alex ten Brink

@Alex Das ist ein guter Punkt, über den ich nicht nachgedacht habe.

Sep2k

13

Nach dem Gap-Theorem (unter Verwendung der Formulierung von hier , suche nach 'Gap') gibt es für jede berechenbare unbegrenzte Funktion einige zunehmende (tatsächlich beliebig große) berechenbare Funktion so dass . $g : \mathbb{N} \rightarrow \mathbb{N}$ $f : \mathbb{N} \rightarrow \mathbb{N}$ $DTIME(f(n)) = DTIME(g(f(n))$

Ihre Frage damit beantwortet, dass es existiert eine solche (unendlich viele in der Tat): Für jede berechenbare Funktion , so dass , gibt es eine steigende Funktion , so dass alle Probleme in auflösbar Zeit ist auch lösbar in Zeit. Beachten Sie, dass nicht unbedingt zeitkonstruierbar ist - für den zeitkonstruierbaren Fall siehe die Antwort von @RanG. $f$ $g$ $g = o(n)$ $f$ $O(f(n))$ $O(g(f(n)) = o(f(n))$ $f$

In der Wikipedia-Formulierung (für die erforderlich ist ) wird zu Ihrem Beispiel, und muss (also gehen Sie andersherum - Probleme, die in lösbar sind) sind auch lösbar in 'ist der interessante Teil). $g(x) \geq x$ $g \circ f$ $f$ $\omega(n)$ $O(g(f(n))$ $O(g(n))$

Der Wikipedia-Artikel bemerkt nicht, dass zunimmt und tatsächlich beliebig groß sein kann (zum Beispiel ). Der Artikel, der den Lückensatz beweist, erwähnt und beweist dies (siehe hier zum Beispiel). $f$ $f(n) \geq g(n)$

Alex ten Brink
quelle

kann sein ? Ist es nicht erforderlich, dass ? Ihre Aussage ist immer noch richtig, aber der Beweis geht in die andere Richtung, oder?

g

$g$

o (n)

$o(n)$

g (x) \geq x

$g(x)\ge x$

Ran G.

@RanG. Aktualisiert, um einen Beweis für beide Formulierungen zu geben (ich habe die Formulierung im Papier verwendet) :)

Alex ten Brink

Für jede berechenbare Funktion g, so dass g = o (n) ist, gibt es eine Funktion f, so dass alle in O (f (n)) -Zeit lösbaren Probleme auch in O (g (f (n)) = o (lösbar sind. f (n)) time "Was ist, wenn alle für dieses g existierenden fs in O (1) sind? Dann ist O (g (f (n)) immer noch O (1) und somit nicht o (1).

sepp2k

@ sepp2k: guter Fang, das ist ja ein Thema wie formuliert. Ich habe meine Antwort aktualisiert.

Alex ten Brink

12

Für jede berechenbare Funktion gibt es ein Problem, das bestenfalls in Zeit gelöst werden kann, oder gibt es eine berechenbare Funktion so dass jedes Problem, das in gelöst werden kann, gelöst werden kann auch in Zeit gelöst werden? $f$ $\Theta(f(n))$ $f$ $O(f(n))$ $o(f(n))$

Wenn ist eine zeit konstruierbar Funktion , dann ist die Zeithierarchie Theorem besagt , dass es Probleme gibt , die erfordern Zeit und kann nicht mit der Zeit gelöst werden . Insbesondere $f$ $O(f(n))$ $o\left (\frac{f(n)}{\log(f(n))}\right )$

DTIME (o (\frac{f (n)}{\log (f (n))})) ⊊ DTIME (f (n))

$\text{DTIME}\left ( o\left (\frac{f(n)}{\log(f(n))}\right) \right ) \subsetneq \text{DTIME} \left ( f(n) \right)$

Dies berücksichtigt nur Entscheidungsprobleme und nicht die Zeit, die zum Generieren der Ausgabe benötigt wird.

Ran G.
quelle

Habe ich Recht, wenn wir nicht-zeitkonstruierbare Funktionen betrachten, lautet die Antwort auf meine Frage "nein"? Oder verwandt: Wenn eine Funktion nicht zeitkonstruierbar ist und es daher keine Turing-Maschine gibt, die nach Schritten anhält , heißt das, dass es auch keine Turing-Maschine gibt, die nach Schritten anhält ? Denn daraus würde sich trivial ergeben, dass die Antwort auf meine Frage nein ist.

f

$f$

f (n)

$f(n)$

Θ (f (n))

$\Theta(f(n))$

8.

Es hängt davon ab, ob. Angenommen, ist nicht zeitkonstruierbar , kann aber durch eine andere Funktion begrenzt werden, die ist. und es gibt immer noch Probleme, die mit der Zeit gelöst werden können, aber nicht zu viel weniger als das.

f

$f$

g

$g$

f = Θ (g)

$f=\Theta(g)$

O (f)

$O(f)$

Ran G.

Wenn Sie mehrere Band-TMs verwenden, können Sie das Ergebnis von auf verbessern .

o (\frac{f (n)}{\lg f (n)})

$o(\frac{f(n)}{\lg f(n)})$

o (f (n))

$o(f(n))$

Kaveh

3

Ich werde versuchen, einen Rahmen zu schaffen, in der Hoffnung, dass er einen tieferen Einblick gewährt.

Wenn Sie zu etwas so grundlegendem gelangen, gibt es überall unerwartete Fallstricke. Zum Beispiel: Was ist es, ein Problem zu "lösen"? In der Informatik betrachten wir oft nur die "Entscheidungs" -Variante, in der wir eine Eingabe erhalten und nur Wahr oder Falsch ausgeben müssen. Sie konzentrieren sich auf das Problem "Funktion".

Wenn Sie die O (f (n)) - Notation als Versuch ansehen, zu erfassen, wie viel "Arbeit" erforderlich ist, um ein Problem zu lösen, erscheint die Verwendung von Entscheidung anstelle von Funktion (wo Ausgabe erforderlich ist) besser, da Sie die Berechnung sauber von der Ausgabeformatierung trennen .

Ich glaube nicht, dass dies Ihre Frage beantworten wird, aber das könnte Sie interessieren: http://en.wikipedia.org/wiki/Time_hierarchy_theorem

Seien Sie auch vorsichtig mit dem Beschleunigungssatz .

agorenst
quelle

Gibt es für jede berechenbare Funktion

Antworten: