Definisi kesetaraan konstruktivitas waktu

Kami mengatakan bahwa fungsi $f:\mathbb{N}\rightarrow\mathbb{N}$ adalah konstruktif-waktu , jika ada mesin Turing multi-tape deterministik $M$ yang pada semua input panjang $n$ membuat paling banyak $f(n)$ langkah dan untuk setiap $n$ ada beberapa input dari panjang $n$ di mana $M$ membuat dengan tepat $f(n)$ langkah.

Kami mengatakan bahwa fungsi $f:\mathbb{N}\rightarrow\mathbb{N}$ adalah sepenuhnya waktu-constructible , jika ada seorang deterministik multi-pita Turing mesin $M$ yang pada semua masukan dari panjang $n$ membuat persis $f(n)$ langkah.

T1: Apakah ada fungsi yang konstruktif-waktu dan tidak sepenuhnya konstruktif-waktu?

Jawabannya adalah ya (lihat jawaban ini ), jika $EXP-TIME \neq NEXP-TIME$ . Bisakah kondisi untuk "ya" diperkuat ke $P\neq NP$ ? Bisakah "ya" dibuktikan?

T2: Apakah kelas fungsi constuctible waktu (sepenuhnya) berubah jika kita hanya mengizinkan mesin Turing 2-pita dalam definisi?

T3: Apa alasan "dapat dibuktikan" untuk meyakini bahwa semua fungsi yang bagus sepenuhnya dapat dibangun waktu?

Makalah
Kojiro Kobayashi: On Proving Time Constructibility of Function. Teor Komputasi. Sci. 35: 215-225 (1985)
menjawab sebagian Q3. Ringkasan parsial dan peningkatannya ada di jawaban ini . Saya mengambil Q3 sebagai jawaban.

Secara historis, gagasan fungsi yang dapat dihitung waktu-nyata digunakan sebagai pengganti (sepenuhnya) konstruktif-waktu. Lihat pertanyaan ini untuk lebih lanjut.

Dalam beberapa hari terakhir saya banyak berpikir tentang fungsi konstruksi-penuh (sepenuhnya) dan saya akan mempresentasikan apa yang saya temukan dengan menjawab Q1 dan Q3. Q2 sepertinya terlalu sulit.

Q3:

Kobayashi dalam artikelnya (rujukannya ada dalam pertanyaan) membuktikan bahwa fungsi , yang terdapat ϵ > 0 st f ( n ) ≥ ( 1 + ϵ ) n , sepenuhnya dapat dibangun jika dihitung dalam waktu O ( f ( n ) ) . (perhatikan bahwa tidak relevan apakah input atau output dalam unary / binary karena kita dapat mengubah antara dua representasi ini dalam waktu linier). Ini membuat fungsi-fungsi berikut ini sepenuhnya dapat dibangun dengan waktu: 2 n ,$f:\mathbb{N}\rightarrow\mathbb{N}$$\epsilon>0$$f(n)\geq (1+\epsilon)n$$O(f(n))$$2^n$ , n ! , n ⌊ log n ⌋ , semua polinomial p lebih dari N st p ( n ) ≥ ( 1 + ϵ ) n ... Kobayashi juga membuktikan konstruktivitas waktu sepenuhnya untuk beberapa fungsi yang tumbuh lebih lambat daripada ( 1 + ϵ ) n , seperti n + ⌊ ⌊ log n ⌋ q ⌋ untuk q ∈ Q + ...$2^{2^n}$$n!$$n\lfloor \log n \rfloor$$p$$\mathbb{N}$$p(n)\geq (1+\epsilon)n$$(1+\epsilon)n$$n+\lfloor\lfloor\log n\rfloor^q\rfloor$$q\in\mathbb{Q}^+$

Untuk melanjutkan dengan contoh-contoh fungsi yang dibangun sepenuhnya waktu, orang dapat membuktikan bahwa jika dan f 2 sepenuhnya dapat dibangun waktu, maka f 1 + f 2 , f 1 f 2 , f f 2 1 dan f 1 ∘ f 2 adalah juga sepenuhnya time-constructible (selanjutnya mengikuti langsung dari Teorema 3.1 di Kobayashi). Ini sekaligus meyakinkan saya bahwa banyak fungsi yang bagus memang sepenuhnya dapat dibangun waktu.$f_1$$f_2$$f_1+f_2$$f_1f_2$$f_1^{f_2}$$f_1\circ f_2$

Sangat mengejutkan bahwa Kobayashi tidak melihat cara untuk membuktikan sepenuhnya konstruk waktu dari fungsi (baik) (dan saya juga tidak).$\lfloor n\log n\rfloor$

Let us also comment the definition from Wikipedia article: A function $f$ is time-constructible, if there exists a Turing machine $M$ which, given a string $1^n$, outputs $f(n)$ in $O(f(n))$ time. We see that this definition is equivallent to our definition of fully time-constructibility for functions $f(n)\geq (1+\epsilon)n$.

Q1:

This question has a really interesting answer. I claim that if all time-constructible functions are fully time-constructible, then $EXP-TIME=NEXP-TIME$. To prove that, let us take an arbitrary problem $L\in NEXP-TIME$, $L\subseteq\{0,1\}^*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a NDTM $M$ in $2^{n^k-1}$ steps. We can assume that at each step $M$ goes in at most two different states for simplicity. Now define the function

I claim that $f$ is time-construcible. Consider the following deterministic Turing machine $T$:

• on input $w$ of length $n$ it computes $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ in $O(n)$ time
• then it simulates $M$ on these bits, where the bits of $w$ determine which (formerly nondeterminisic) choices to take.
• accept iff $\left(M\textrm{ accepts using choices given by }w\right)$.

Note that the length of $w$ ($=n$) is enough that it determines all nondeterministic choices, since $M$ on input $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ makes at most $n$ steps.

We can make $T$ run in at most $8n+1$ steps. Now the following Turing machine proves that $f$ is time-constructible:

• on input $w$ of length $n$ run $T$ and count steps in parallel so that exacly $8n$ steps are done.
• if $T$ rejected or would reject in the next step, go to a halting state in the next step. Else, make one more step and then go to a halting state.

Now suppose that $f$ is fully time-constructible. We will prove that this leads to $EXP-TIME=NEXP-TIME$.

The following algorithm solves $L$:

• on input $x$, let $n$ be the number with binary representation $x00\ldots 0$ ($|x|^{k-1}$ zeros). It follows that $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$.
• compute $f(n)$ in time $f(n)$ and check whether it is divisible by 2.

This algorithm runs in exponential time and solves $L$. Since $L\in NEXP-TIME$ was arbitrary, $EXP-TIME=NEXP-TIME$.