Verifying time complexity of Turing machinesGajser, David (Avtor) Cabello, Sergio (Mentor) Mohar, Bojan (Komentor) Turing machinerelativizationNP-completenesscrossing sequencedecidabilitylower boundtime complexityrunning timelinear timeThe 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.[D. Gajser]20152017-09-22 02:54:07Doktorsko delo/naloga95862sl