Memisahkan kelas waktu

Seorang murid saya baru-baru ini mengajukan pertanyaan berikut:

AsumsikanHaruskah ada sedemikian rupa sehingga

D T I M E (f (n)) ⊊ D T I M E (g (n)) .

$DTIME(f(n)) \subsetneq DTIME(g(n)).$

h(n) $h(n)$

D T I M E (f (n)) ⊊ D T I M E (h (n)) ⊊ D T I M E (g (n)) ?

$DTIME(f(n)) \subsetneq DTIME(h(n)) \subsetneq DTIME(g(n))?$

Ini mungkin dapat ditunjukkan benar dengan membangun jika adalah konstruktif waktu. Tetapi secara umum, saya merasa bahwa ini harus salah mirip dengan . $h(n)$ $f,g$ $DSPACE(o(\log(\log(n)))) = DSPACE(1)$

cc.complexity-theory S. Pek
sumber

Ini mungkin tergantung pada model yang tepat.

Teorema kesenjangan Borodin yang disebutkan di sini mungkin relevan: cstheory.stackexchange.com/questions/8583/…

Michael Wehar

Apakah Anda mengizinkan ? Karena dengan demikian beberapa contoh harus ada untuk beberapa fungsi yang nol di mana-mana, kecuali tempat pertama. Bagaimanapun, bukankah pertanyaan ini masuk akal jika mana-mana kecuali satu ?

f(n),g(n)=O(1) $f(n),g(n)=O(1)$

f≡g $f\equiv g$

n $n$

domotorp

Maaf saya tidak cukup mengikuti masalah dengan seperti definisi ?

f(n),g(n)=O(1) $f(n),g(n) = O(1)$

DTIME(f(n))=DTIME(g(n)) $DTIME(f(n))=DTIME(g(n))$

S. Pek

Maaf tentang itu, saya salah membaca pertanyaan dan komentar saya sebelumnya tidak masuk akal. Saya menghapusnya. Terima kasih.

Michael Wehar

Jawaban:

Jika $DTIME(f(n))$ didefinisikan sebagai kelas semua bahasa yang dapat dipilih dalam waktu $O(f(n))$ oleh mesin Turing dua pita, maka saya curiga bahwa jawabannya adalah tidak. Dengan kata lain, saya pikir tidak selalu ada kelas kompleksitas waktu menengah yang ketat.

Catatan: Jawaban ini mungkin tidak persis seperti yang Anda cari karena saya mempertimbangkan fungsi yang tidak dapat dihitung dan saya tidak menyertakan setiap detail argumen. Tapi, saya merasa itu adalah awal yang baik. Silahkan mengajukan pertanyaan. Mungkin saya dapat mengisi rincian ini lebih lanjut di beberapa titik atau mungkin ini akan menghasilkan jawaban yang lebih baik dari pembaca yang tertarik.

Pertimbangkan fungsi dari bentuk $f : \mathbb{N} \rightarrow \mathbb{N}$ . Kami menyebut fungsi-fungsi ini sebagai fungsi bilangan alami.

Klaim 1: Saya mengklaim bahwa kita dapat membangun fungsi bilangan alami (tidak dapat dikomputasi) yang sangat lambat tumbuh $\varepsilon(n)$ sedemikian rupa sehingga:

(1) $\varepsilon(n)$ tidak menurun

(2) $\varepsilon(n) = \omega(1)$

(3) Untuk semua komputer yang tidak terbatas, $f: \mathbb{N} \rightarrow \mathbb{N}$ , himpunan $\{ n \; \vert \; \varepsilon(n) \leq f(n) \}$ tidak terbatas.

Kami membangun sebagai fungsi langkah non-menurun yang tumbuh lambat. Mari kita menghitung semua fungsi komputasi terbatas . Kami ingin membangun sedemikian rupa sehingga untuk setiap dan setiap , $\varepsilon(n)$ $\{ f_i \}_{i \in \mathbb{N}}$ $\varepsilon(n)$ $i$ $j \leq i$ . Dengan kata lain, kita menunggu untuk memetakan ke sampaifungsi pertamadalam penghitungan telah dipetakan ke nilai yang lebih besar dari atau sama dengan setidaknya sekali. Kemudian, terus memetakan ke hingga fungsi pertamadalam penghitungan telah dipetakan ke nilai yang lebih besar dari atau sama dengan setidaknya sekali dan pada titik ini mulai memetakan ke $min\{ k \; \vert \; \varepsilon(k) \geq i\} \geq min\{ k \; \vert \; f_{j}(k) \geq i \}$ $\varepsilon(n)$ $i$ $i$ $i$ $\varepsilon(n)$ $i$ $i+1$ $i+1$ $i+1$ . Jika kita melanjutkan proses berulang ini untuk membangun , maka untuk setiap fungsi komputabel yang diberikan tidak terikat, meskipun mungkin tidak selalu lebih kecil, itu akan sering kali paling tidak setidaknya sama kecil. $\varepsilon(n)$ $\varepsilon(n)$

Catatan: Saya baru saja memberikan intuisi di balik klaim 1, saya tidak memberikan bukti terperinci. Silakan bergabung dalam diskusi di bawah ini.

Karena adalah fungsi yang tumbuh sangat lambat, kami memiliki yang berikut: $\varepsilon(n)$

Klaim 2: Untuk semua fungsi bilangan asli yang dapat dihitung dan , jika $f(n)$ $h(n)$ dan, lalu. $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ $h(n) = O(f(n))$ $h(n) = \Theta(f(n))$

Untuk klaim 2, jika ada fungsi yang dapat dihitung antara $h(n)$ dansedemikian rupa sehingga, maka kita akan dapat menghitung fungsi bilangan alami tak terbatas yang tumbuh lebih lambat dariyang tidak mungkin . $\frac{f(n)}{\varepsilon(n)}$ $f(n)$ $h(n) \neq \Theta(f(n))$ $\varepsilon(n)$

Biarkan saya menjelaskan beberapa detail yang relevan. Misalkan demi kontradiksi bahwa fungsi seperti ada. Lalu, $h(n)$ tidak terbatas. $\lfloor \frac{f(n)}{h(n)} \rfloor$

Catatan: Fungsi sebelumnya dapat dihitung karena dan dapat dihitung. $f(n)$ $h(n)$

Karena , kita memiliki $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ . Karena itu ada beberapa konstantasehingga untuk semuacukup besar, $\lfloor \frac{f(n)}{h(n)} \rfloor = O(\varepsilon(n))$ $\alpha$ $n$ . Karena fungsi ini tidak terbatas dan dapat dihitung, kami dapat menerapkan Klaim 1 untuk mendapatkan bahwa $\lfloor \alpha \frac{f(n)}{h(n)} \rfloor < \varepsilon(n)$ $\varepsilon(n) \leq \lfloor \alpha \frac{f(n)}{h(n)} \rfloor$ infinitely often which contradicts the previous statement.

Claim 3: For a time constructible function $f(n)$ , we have that $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$ , yet there does not exist $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(h(n)) \subsetneq DTIME(f(n))$ .

In order to just show that, $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$ we need to use a stronger time hierarchy theorem and this is where we use the assumption that the number of tapes is fixed (we said two tapes above). See "The tight deterministic time hierarchy" by Martin Furer.

Since there are no computable natural number functions between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ other than those that are $\Theta(f(n))$ , we have that for every function $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $h(n) \neq \Theta(f(n))$ , $DTIME(\frac{f(n)}{\varepsilon(n)}) = DTIME(h(n))$ .

Michael Wehar
sumber

Yes, this is exactly what I had in mind too, but then got confused somewhere along the way. I just want to note, that

ϵ(n) $\epsilon(n)$ needn't be small at all; a similar argument shows that the lower function

f(n)ϵ(n) $\frac{f(n)}{\epsilon(n)}$ can be replaced with a function that is always either

f(n) $f(n)$ or

0 $0$ , and the upper function

f(n)ϵ(n) $f(n)\epsilon(n)$ can be replaced with a function that is always either

f(n) $f(n)$ or

∞ $\infty$ .

domotorp

(3) needs to restrict to unbounded functions

f $\hspace{.04 in}f$ .

@RickyDemer Yes, you are right! Thank you very much for catching that. I edited my answer to add the word unbounded. :)

Michael Wehar

Im not entirely convinced about Claim 1. Consider

fi(n)=1 $f_i(n) = 1$ if

n≤i $n \leq i$ ,

n−i $n-i$ otherwise. Considering this enumeration, is

ϵ(n)=Θ(1) $\epsilon(n) = \Theta(1)$ ?

S. Pek

I have two more concerns of this proof: 1) In claim 2 you said that the contradiction arises from the fact that there cannot exist a computable

ϵ(n) $\epsilon(n)$ as it equals

|h(n)−f(n)| $|h(n)-f(n)|$ . I believe this to be a typographical error, as it should say there exist a

k′ $k'$ such that

ϵ(n)=|h(n)−k′⋅f(n)| $\epsilon(n) = |h(n) - k'\cdot f(n)|$ . But note that

k′ $k'$ need not be computable, so the argument need not hold. 2) You used the result by Furer in Claim 3. However, the result only holds for time-constructable functions, but

f(n)ϵ(n) $\frac{f(n)}{\epsilon(n)}$ need not be time-constructable.

S. Pek

If this result is true, it would strengthen the best-known deterministic time hierarchy theorem. [This is more of a comment than an answer, but too long for a comment. It leaves open the direct construction of a counterexample.] Recall that the best Deterministic Time Hierarchy Theorem we currently have is that if $f(n), g(n)$ are time-constructible, and $g(n) \leq o( f(n) / \log f(n) )$ , then $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(f(n))$ .

Now suppose your desired result is true, and let $g(n)$ be a time-constructible function that is close to, but still little-oh of, $f(n) / \log(f(n))$ , say, $g(n) = f(n) / (\log f(n))^{3/2}$ . (This $g$ may not be time-constructible for arbitrary time-constructible $f$ , but surely for many time-constructible $f$ this $g$ is also time-constructible.) Now, your desired result produces an $h$ such that $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(h(n)) \subsetneq \mathsf{DTIME}(f(n))$ . In order to avoid improving the current-best time hierarchy theorem, we would need both $g(n) = o( h(n) / \log(h(n)) )$ and $h(n) = o(f(n) / \log(f(n))$ . These two together imply that $g(n) \leq o( f(n) / (\log(f(n)) \log(h(n)))$ . Since $h(n) \geq g(n)$ , we have $g(n) \leq o( \frac{f(n)}{\log(f(n)) \log(g(n))})$ , or equivalently $g(n) \log g(n) \leq o(f(n) / \log(f(n)))$ . But $g(n) \log(g(n)) = f(n) / (\log(f(n))^{3/2} [\log(f(n)) - (3/2) \log \log(f(n)] \sim f(n) / \sqrt{\log(f(n))}$ , which is not $o(f(n) / \log(f(n))$ .

Joshua Grochow
sumber

Cool! Also, note that there is a better time hierarchy theorem if the number of tapes is fixed. See "The tight deterministic time hierarchy" by Martin Furer.

Michael Wehar

@MichaelWehar: Thanks for the pointer! Indeed, when one gets so tight as to only require

g(n)=o(f(n)) $g(n) = o(f(n))$ , as Furer shows when the number of tapes is fixed, then my argument goes away. (And for basically the same reason, my argument goes away if this question were about space hierarchy instead of time: for space we have a perfectly tight hierarchy theorem even if # tapes isn't fixed.)

Joshua Grochow

I think such a behaviour is true for 1-Tape-DTMs. On the one hand, we have $\mathrm{DTIME}_1(O(n)) = \mathrm{DTIME}_1(o(n \log n))$ . Unfortunately, the only reference I know is in German: R. Reischuk, Einführung in die Komplexitätstheorie, Teubner, 1990, Theorem 3.1.8.

On the other hand, it should be possible to separate $\mathrm{DTIME}_1(O(n))$ and $\mathrm{DTIME}_1(O(n \log n))$ by the language $\{ x \#^{2^{|x|}} x \mid x \in \{0,1\}^* \}$ using a standard crossing sequence argument.

Markus Bläser
sumber