Course details

Complexity

SLO Acad. year 2009/2010 Summer semester 5 credits

Current academic year

This course covers the following themes: Matematical models of computation ( skeleton language, RAM, RASP models and their connection with Turing machines), time complexity, complexity classes, P and NP, NP-completness, important NP-complete problems, satisfability problem and its variants, other NP-problems, NP and co-NP languages, space complexity, PS and NPS languages, PS-complete languages, language classes based on randomization, applications of computational complexity theory - cryptography and one-way functions.

Guarantor

Vojnar Tomáš, prof. Ing., Ph.D. (DITS)

Language of instruction

Czech

Completion

Examination

Time span

  • 26 hrs lectures
  • 26 hrs projects

Department

Department of Intelligent Systems (UITS)

Subject specific learning outcomes and competences

Understanding theoretical and practical limits of arbitrary computational systems.

Learning objectives

To learn mathematical models of computation and complexity theory.

Prerequisite knowledge and skills

There are no prerequisites

Study literature

  • Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
  • Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
  • Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
  • Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X
  • Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1-846-28297-7

Fundamental literature

  • Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
  • Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
  • Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1

Syllabus of lectures

  • Introduction. Complexity, time and space complexity.
  • Matematical models of computation. Skeleton language.
  • RAM, RASP machines and their relation with Turing machines.
  • Nondeterminism. Oracle machines. Reducibility.
  • P and NP. Examples: Kruskal, Traveling Salesman.
  • NP-completness. NP-complete problems.
  • Satisfability problem and its variants.
  • Other NP-problems.
  • NP and co-NP languages.
  • Space complexity, PS and NPS languages.
  • PS-complete languages.
  • Language classes based on randomization - classes RP and ZPP.
  • Applications: Cryptography and one-way functions.

Progress assessment

Study evaluation is based on marks obtained for specified items. Minimimum number of marks to pass is 50.

Controlled instruction

Projects.

Course inclusion in study plans

Back to top