Search

V delu definiramo verjetnostne kontekstno-neodvisne gramatike in opišemo njihovo uporabo v simbolni regresiji. Omejimo se na gramatike, ki tvorijo algebrajske izraze in natančno definiramo izraz. Motiviramo problem izračuna verjetnosti podanega izraza za podano gramatiko in dokažemo, da je v splošnem neodločljiv. Predstavimo nekaj posebnih primerov gramatik, ki generirajo izraze, za katere je problem algoritmično rešljiv. Podamo postopek za izračun verjetnosti podanega izraza za te posebne primere gramatik. Na koncu predstavimo verjetnostne gramatike, ki generirajo podmnožice grup. We define probability context-free grammars and describe their use for symbolic regression. We study grammars that generate algebraic expressions and meticulously define an expression. We show that calculating the probability of a given expression for a given grammar is generally undecidable. We overview specific grammars for generating expressions, where an algorithm for calculating the probability of a given expression exists. For those example grammars, we present an algorithm for calculating the probability of a given expression. At last, we present probabilistic grammars for generating elements from groups.

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}(nlog 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(nlog 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}(nlog 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 ▫$Cgeq 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. 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}(nlog n)$▫ možno z algoritmom preveriti, ali je časovna zahtevnost danega enotračnega Turingovega stroja ▫$T(n)$▫. Meja ▫$operatorname{o}(nlog n)$▫ je tesna, saj za ▫$T(n) = Omega(nlog 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}(nlog 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{Pstackrel{?}{=}NP}$▫.