izpis_h1_title_alt

Verifying time complexity of Turing machines : doctoral thesis
ID Gajser, David (Avtor), ID Cabello, Sergio (Mentor) Več o mentorju... Povezava se odpre v novem oknu, ID Mohar, Bojan (Komentor)

.pdfPDF - Predstavitvena datoteka, prenos (881,68 KB)
MD5: 4F74C1FEA4CB045968A2D5B08B753EAE
PID: 20.500.12556/rul/194ea351-86a6-408d-ad0b-79d8425e0975

Izvleček
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 Povezava se odpre v novem oknu
UDK:510.582(043.3)
COBISS.SI-ID:282124800 Povezava se odpre v novem oknu
Datum objave v RUL:24.10.2017
Število ogledov:1211
Število prenosov:679
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

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

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj