The course provides students with knowledge of basic as well as selected advanced topics in computability and complexity. The first part deals with decision problems, languages, and decidability of problems. The second part is devoted to the results of complexity theory. The students are acquainted with selected topics of time and space complexity (classes of languages/problems P, NP, NP-complete, PSPACE, PSPACE-complete) and further advanced topics, e.g., relativization, problems decidable in sublinear space, probabilistic algorithms, etc. 1. Formal models of computation Turing machines, formalized computation, languages recognizable by Turing machines, languages decided by Turing machines, Turing-computable function, Church-Turing thesis. Variants of Turing machines: machine with multiple tapes. Universal Turing machine. Equivalence of various computation models. 2. Languages and problems The relationship between languages and (decision) problems. Partial recursive and recursive languages, decision problems. Diagonalization. Turing-undecidable languages. Turing-unrecognizable language. Selected undecidable problems: acceptance problem, halting problem, Post correspondence problem. Relationship of partial recursive and recursive languages to languages from the Chomski hierarchy. 3. Recursion theorem and further results Rice theorem, recursion theorem, and their applications. Further models of computation: Post machines, non-deterministic Turing machines, probabilistic Turing machines, fuzzy Turing machines. Decidability and undecidability of (logical) theories. 4. Introduction the the complexity theory Asymptotic complexity of algorithms. Big-O, small-o, big-theta notation. Time complexity. Classes P, NP. P-NP problem. Polynomial-time reducibility. Class of NP-complete problems and its importance. Selected NP-complete problems, basic methods to prove NP-completeness, Cook-Levin theorem. Applications of hard problems. 5. Space complexity and further issues Classes PSPACE, NPSPACE, time and space constructibility, Savitch theorem. PSPACE-complete problems. Problems solvable in sublinear space, classes L, NL, and co-NL. Time and space hierarchy theorems. Relativization. Probabilistic algorithms, alternating Turing machines and complexity.
|
-
Gruska J. (1997). Foundations of Computing. International Thompson Computer Press.
-
Hopcroft J. E., Motwani R., Ullman J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston.
-
Kozen D. C. (1997). Automata and Computability. Springer.
-
Kozen D. C. (1991). The Design And Analysis of Algorithms. Springer.
-
Leeuwen van, J. (1994). Handbook of Theoretical Computer Science, Vol. A: Algorithms. The MIT Press.
-
Lewis H. R., Papadimitriou C. H. (1994). Computational Complexity. Reading (Mass.), Addison Wesley.
-
Sedgewick S., Flajolet P. (1996). Analysis of Algorithms. Addison-Wesley.
-
Sipser M. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.
|