-
Verifying time complexity of Turing machines : doctoral thesisGajser, David, 1987-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}$▫.Type of material - dissertation ; adult, seriousPublication and manufacture - Ljubljana : [D. Gajser], 2015Language - englishCOBISS.SI-ID - 282124800
Link(s):
http://www.matknjiz.si/doktorati/2015/Gajser-14521-18.pdf
Repository of the University of Ljubljana – RUL
Digitalna knjižnica Slovenije - dLib.siDostop z namenskih računalnikov v prostorih NUK
Author
Gajser, David, 1987-
Other authors
Cabello, Sergio |
Mohar, Bojan, 1956-
Topics
Turingovi stroji |
Disertacije |
relativizacija |
NP-polnost |
prekrižno zaporedje |
odločljivost |
spodnja meja |
časovna zahtevnost |
čas izvajanja |
linearni čas |
Turing machine |
relativization |
NP-completeness |
crossing sequence |
decidability |
lower bound |
time complexity |
running time |
linear time
Library/institution |
City | Acronym | For loan | Other holdings |
---|---|---|---|---|
FMF and IMFM, Mathematical Library, Ljubljana | Ljubljana | MAKLJ |
reading room 1 cop.
|
|
National and University Library, Ljubljana | Ljubljana | NUK |
reading room 1 cop.
|
not for loan 1 cop.
|
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Gajser, David, 1987- | 34564 |
Cabello, Sergio | 25993 |
Mohar, Bojan, 1956- | 01931 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.