-
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}$▫.Vrsta gradiva - disertacija ; neleposlovje za odrasleZaložništvo in izdelava - Ljubljana : [D. Gajser], 2015Jezik - angleškiCOBISS.SI-ID - 282124800
Povezava(-e):
http://www.matknjiz.si/doktorati/2015/Gajser-14521-18.pdf
Repozitorij Univerze v Ljubljani – RUL
Digitalna knjižnica Slovenije - dLib.siDostop z namenskih računalnikov v prostorih NUK
Avtor
Gajser, David, 1987-
Drugi avtorji
Cabello, Sergio |
Mohar, Bojan, 1956-
Teme
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
Knjižnica/institucija |
Kraj | Akronim | Za izposojo | Druga zaloga |
---|---|---|---|---|
FMF in IMFM, Matematična knjižnica, Ljubljana | Ljubljana | MAKLJ |
v čitalnico 1 izv.
|
|
Narodna in univerzitetna knjižnica, Ljubljana | Ljubljana | NUK |
v čitalnico 1 izv.
|
ni za izposojo 1 izv.
|
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Gajser, David, 1987- | 34564 |
Cabello, Sergio | 25993 |
Mohar, Bojan, 1956- | 01931 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.