Verifying time complexity of Turing machines : doctoral thesis

Gajser, David (avtor), Cabello, Sergio (mentor), Mohar, Bojan (komentor)

The central problem in the dissertation is the following: "For a function $T \colon \mathbb{N} \rightarrow \mathbb{R}_{\,\geq 0}$, how hard is it to verify whether a given Turing machine runs in time at most $T(n)$? Is it even possible?" Our first main contibution is that, for all reasonable functions $T(n) = \operatorname{o}(n\log n)$, it is possible to verify with an algorithm whether a given one-tape Turing machine runs in time at most $T(n)$. This is a tight bound on the order of growth for the function $T$ because we prove that, for $T(n) = \Omega(n\log n)$ and $T(n)\geq n+1$, there exists no algorithm that would verify whether a given one-tape Turing machine runs in time at most $T(n)$. As opposed to one-tape Turing machines, we show that we can verify with an algorithm whether a given multi-tape Turing machine runs in time at most $T(n)$ if and only if $T(n_0) < n_0+1$ for some $n_0 \in \mathbb{N}$. Linear time bounds are the most natural algorithmically verifiable time bounds for one-tape Turing machines, because a one-tape Turing machine that runs in time $\operatorname{o}(n\log n)$ actually runs in linear time. This motivates our second main contibution which is the analysis of complexity of the following family of problems, parameterized by integers $C\geq 2$ and $D \geq 1$: "Does a given one-tape $q$-state Turing machine run in time $Cn+D$?" Assuming a fixed tape and input alphabet, we show that these problems are co-NP-complete and we provide good lower bounds. Specifically, these problems cannot be solved in $\operatorname{o}(q^{(C-1)/4})$ non-deterministic time by multi-tape Turing machines. We also show that the complements of these problems can be solved in $\operatorname{O}(q^{C+2})$ non-deterministic time and not in $\operatorname{o}(q^{(C-1)/4})$ non-deterministic time by multi-tape Turing machines. To prove the upper bound $\operatorname{O}(q^{C+2})$, we use the so-called compactness theorem which is our third main contribution. We need more notation to state it in full generality, but a simple corollary tells the following: To verify whether an input one-tape Turing machine runs in time $Cn+D$, it is enough to verify this on a finite number of inputs. We argue that our main results are proved with techniques that relativize and that using only such techniques we cannot solve the P versus NP problem.

• Jezik: Angleški jezik
• Ključne besede: Turing machine, relativization, NP-completeness, crossing sequence, decidability, lower bound, time complexity, running time, linear time
• Vrsta gradiva: Doktorsko delo/naloga
• Tipologija: 2.08 - Doktorska disertacija
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Kraj izida: Ljubljana
• Založnik: [D. Gajser]
• Leto izida: 2015
• Št. strani: X, 120 str.
• PID: 20.500.12556/RUL-95862
• UDK: 510.582(043.3)
• COBISS.SI-ID: 282124800
• Datum objave v RUL: 24.10.2017

GAJSER, David, 2015, Verifying time complexity of Turing machines : doctoral thesis [na spletu]. Doktorska disertacija. Ljubljana : D. Gajser. [Dostopano 25 april 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=95862

Sekundarni jezik

• Jezik: Slovenski jezik
• Naslov: Preverjanje časovne zahtevnosti Turingovih strojev

Izvleček

Osrednji problem v disertaciji je sledeč: "Naj bo $T \colon \mathbb{N} \rightarrow \mathbb{R}_{\,\geq 0}$ poljubna funkcija. Kako težko je preveriti, ali je časovna zahtevnost danega Turingovega stroja $T(n)$? Je to sploh mogoče preveriti?" Naš prvi večji prispevek pove, da je za vse "normalne" funkcije $T(n)=\operatorname{o}(n\log n)$ možno z algoritmom preveriti, ali je časovna zahtevnost danega enotračnega Turingovega stroja $T(n)$. Meja $\operatorname{o}(n\log n)$ je tesna, saj za $T(n) = \Omega(n\log n)$ in $T(n)\geq n+1$ ni mogoče z algoritmom preveriti, ali je časovna zahtevnost danega enotračnega Turingovega stroja $T(n)$. Pri večtračnih Turingovih strojih je rezultat enostavnejši. Zanje namreč velja, da je časovno zahtevnost $T(n)$ moč z algoritmom preveriti natanko tedaj, ko velja $T(n_0) < n_0+1$ za neki $n_0 \in \mathbb{N}$. Znano je, da je vsak enotračni Turingov stroj časovne zahtevnosti $\operatorname{o}(n\log n)$ tudi linearne časovne zahtevnosti. Posledično je linearna časovna zahtevnost najbolj naravna časovna zahtevnost, ki jo lahko z algoritmom preverimo pri enotračnih Turingovih strojih. V disertaciji se zato ukvarjamo tudi z naslednjimi problemi, ki so parametrizirani z naravnima številoma $C \geq 2$ in $D \geq 1$: "Ali je dani enotračni Turingov stroj s $q$ stanji časovne zahtevnosti $Cn+D$?" Pri analizi teh problemov, kar je naš drugi večji prispevek, predpostavljamo fiksno vhodno in tračno abecedo. Ti problemi so co-NP-polni in zanje lahko dokažemo dobre spodnje meje računske zahtevnosti. Ni jih namreč mogoče rešiti v času $\operatorname{o}(q^{(C-1)/4})$ z nedeterminističnimi večtračnimi Turingovimi stroji. Še več, komplementi teh problemov so rešljivi z večtračnimi nedeterminističnimi Turingovimi stroji v času $\operatorname{O}(q^{C+2})$, ne pa v času $\operatorname{o}(q^{(C-1)/4})$. Pri dokazu zgornje meje $\operatorname{O}(q^{C+2})$ uporabimo tako imenovani izrek o kompaktnosti, naš tretji večji prispevek. Potrebovali bi več notacije, da bi ga na tem mestu navedli, zato povejmo le njegovo posledico: Da bi preverili, ali dani enotračni Turingov stroj teče v času $Cn+D$, je dovolj preveriti čas izvajanja Turingovega stroja le na končno mnogo vhodih. Glavni prispevki te disertacije so dokazani s tehnikami, ki relativizirajo. Dokažemo tudi znano dejstvo, da s takimi tehnikami ni mogoče rešiti slavnega problema $\rm{P\stackrel{?}{=}NP}$.

• Ključne besede: Turingovi stroji, relativizacija, NP-polnost, prekrižno zaporedje, odločljivost, spodnja meja, časovna zahtevnost, čas izvajanja, linearni čas