Czy dla każdej funkcji obliczalnej

19

Czy dla każdej funkcji obliczalnej $f$ istnieje problem, który można najlepiej rozwiązać w czasie $\Theta(f(n))$ czy też istnieje funkcja obliczalna $f$ tak że każdy problem, który można rozwiązać w $O(f(n))$ może również być rozwiązany w czasie $o(f(n))$ ?

To pytanie wpadło mi do głowy wczoraj. Zastanawiam się przez chwilę, ale nie mogę tego rozgryźć. Naprawdę nie wiem, jak to zrobić w Google, więc pytam tutaj. Oto, co wymyśliłem:

Moją pierwszą myślą było, że odpowiedź brzmi tak: dla każdej funkcji obliczeniowej $f$ problemu „Wyjście $f(n)$ kropek” (lub utworzenie ciągu z $f(n)$ kropkami lub cokolwiek innego) oczywiście nie można rozwiązać w $o(f(n))$ czas. Musimy więc tylko pokazać, że można to rozwiązać w czasie $O(f(n))$ . Żaden problem, po prostu weź następujący pseudo kod:

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

Oczywiście ten algorytm rozwiązuje określony problem. I jego czas działania jest oczywiście w $\Theta(f(n))$ , więc problem został rozwiązany. To było łatwe, prawda? Z wyjątkiem nie, to nie dlatego, że musisz wziąć pod uwagę koszt pierwszej linii. Czas trwania powyższego algorytmu jest tylko $\Theta(f(n))$ , jeżeli czas potrzebny do oblicz $f(n)$ w $O(f(n))$ . Oczywiście nie jest to prawdą dla wszystkich funkcji ¹ .

Więc to podejście nigdzie mnie nie doprowadziło. Byłbym wdzięczny za to, że ktoś wskazywałby mi właściwy kierunek, aby poprawnie to rozgryźć.

¹ Rozważmy na przykład funkcję . Oczywiście , ale nie jest algorytm oblicza w czas. $p(n) = \cases{1 & \text{if $n$ is prime} \\ 2 & \text{otherwise}}$ $O(p(n)) = O(1)$ $p$ $O(1)$

complexity-theory

— sepp2k
źródło

1

Nie sądzę, aby twoje dwa stwierdzenia w pierwszych akapitach były dla siebie nawzajem przeciwstawnymi: co jeśli masz taki

, że istnieje jakiś problem, który można rozwiązać w

, a nie w

, ani w

czasie?

f

$f$

O (f (n))

$O(f(n))$

o (f (n))

$o(f(n))$

Θ (f (n))

$\Theta(f(n))$

— Alex ten Brink

@Alex To dobry punkt, że nie brałem tego pod uwagę.

— sepp2k

13

Według twierdzenia Gap (używając sformułowania stąd , szukaj „luki”), dla dowolnej obliczalnej funkcji niezwiązanej istnieje pewna rosnąca (w rzeczywistości dowolnie duża) funkcja obliczeniowa taka, że . $g : \mathbb{N} \rightarrow \mathbb{N}$ $f : \mathbb{N} \rightarrow \mathbb{N}$ $DTIME(f(n)) = DTIME(g(f(n))$

Odpowiada to na twoje pytanie, ponieważ istnieje takie (w rzeczywistości nieskończenie wiele): dla każdej funkcji obliczeniowej takiej, że , istnieje pewna rosnąca funkcja tak że wszystkie problemy rozwiązane w czas można również rozwiązać w czasie . Zauważ, że $f$ $g$ $g = o(n)$ $f$ $O(f(n))$ $O(g(f(n)) = o(f(n))$ $f$ niekoniecznie musi być konstruowany w czasie - w przypadku, w którym można konstruować w czasie, patrz odpowiedź @RanG.

W formule Wikipedii (która wymaga, że ), wtedy staje się twoim przykładem, a musi być (więc odwróć - problemy rozwiązane w są również rozpuszczalne w 'jest interesującą częścią). $g(x) \geq x$ $g \circ f$ $f$ $\omega(n)$ $O(g(f(n))$ $O(g(n))$

Artykuł w Wikipedii nie zauważa, że rośnie i może w rzeczywistości być dowolnie duży (na przykład ). W artykule, który udowadnia twierdzenie szczeliny ma wzmianki i udowodnić (patrz tutaj , na przykład). $f$ $f(n) \geq g(n)$

— Alex ten Brink
źródło

Można

być

? Czy nie jest wymagane, aby

? Twoje oświadczenie jest nadal prawidłowe, ale dowód idzie w drugą stronę, prawda?

g

$g$

o (n)

$o(n)$

g (x) \geq x

$g(x)\ge x$

— Ran G.

@RanG. Zaktualizowano, aby dać dowód na oba preparaty (użyłem tego przepisu w pracy) :)

— Alex ten Brink

"for every computable function g such that g=o(n), there exists some function f such that all problems solvable in O(f(n)) time are also solvable in O(g(f(n))=o(f(n)) time" What if all the fs that exist for that g are in O(1)? Then O(g(f(n)) is still O(1) and thus not o(1).

— sepp2k

@sepp2k: good catch, this is indeed an issue as formulated. I've updated my answer.

— Alex ten Brink

12

For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time or is there a computable function $f$ such that every problem that can be solved in $O(f(n))$ can also be solved in $o(f(n))$ time?

If $f$ is a time-constructible function, then the Time Hierarchy Theorem says that there are problems that require $O(f(n))$ time, and cannot be solved with time $o\left (\frac{f(n)}{\log(f(n))}\right )$ . Specifically,

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)$

This consider only decision problems, and does not regard the time it takes to generate the output.

— Ran G.
źródło

Am I right in assuming that if we consider non-time-constructible functions, the answer to my question is "no"? Or relatedly: if a function

f

$f$ is not time-constructible and thus there is no Turing machine that halts after

f (n)

$f(n)$ steps, does that mean there is also no Turing machine that halts after

Θ (f (n))

$\Theta(f(n))$ steps? Because from that it would trivially follow that the answer to my question is no.

— sepp2k

It depends. Assume

f

$f$ is not time-constructible but can be bounded by some other function

g

$g$ which is time-constructible.

f = Θ (g)

$f=\Theta(g)$ and there still exists problems which can be solved with time

O (f)

$O(f)$ but not too much less than that.

— Ran G.

and using multiple tape TMs, you can improve the result from

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

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

o (f (n))

$o(f(n))$ .

— Kaveh

3

I will try to provide something of a framework in the hopes it grants deeper insight.

When you get to something this fundamental there are unexpected pitfalls everywhere. For example: what is it to "solve" a problem? Often in computer science we consider only the "decision" variant, in which we are given an input and need only to output True or False. You are focusing on the "function" problem.

If you consider O(f(n)) notation as trying to capture how much "work" is needed to solve a problem, using decision instead of function (where output is required) seems better because you cleanly separate the computation from the output formatting.

I don't think this will answer your question, but you may be interested in this: http://en.wikipedia.org/wiki/Time_hierarchy_theorem

Also, be careful about the speedup theorem.

— agorenst
źródło