Theory of Computation
- understand the concepts of the complexity classes P, NP, coNP, #P, EXP, NEXP, L, NL, PSPACE, EXPSPACE, BPP, RP
- be able to critically analyse resources used by a program (and optimize them at a high level)
- be able to recognize intractable problems and categorize their difficulty
- have deeper understanding and trained problem solving skills of known materials in: algebra, probability theory, discrete math, algorithms
- To know the complexity classes P, NP, coNP, #P, EXP, NEXP, L, NL, PSPACE, EXPSPACE, BPP, RP; relations among these classes (including separations through the hierarchy theorems); famous open problems
- To know problems that are complete for NP and PSPACE
- To know algorithms for prime testing and cryptography
- To know several classes in communication complexity
- To know circuit complexity, the classes NC_k and AC_k, and P-completeness
- Complexity classes P and NP, reductions, NP-completeness and hierarchy theoremsIn this topic many fundamental concepts of the course are introduced. We focus mainly on decision problems of sets of bitstrings. For a fixed set, we consider the problem of deciding whether a string belongs to the set.
- L, NL, PSPACE, EXPSPACE, and PSPACE-completeness of some gamesWe define space complexity classes and show that a large group of games are in the class PSPACE. Space is a much stronger resource than time because it can be reused. We prove the space analogue of the P=NP problem, which is called Savitch theorem: PSPACE = NPSPACE. Again we define PSPACE completeness. The decision problem TQBF considers a fully quantified Boolean formula and asks whether this formula is true. We show that this problem is PSPACE-complete. Then we show that finding winning strategies in games corresponds to PSPACE complete problems.
- Oracle computations and oracles the P vs NP problem relative to specific oraclesWe define computation for devices that have access to a device that stores or solves the decision problem for another language.
- Randomized computation and prime testingThe complexity class BPP corresponds to sets that are decidable by a polynomial time algorithm that uses randomness and for each input gives the correct answer with probability 1/3. We show that changing the value 1/3 to any other positive number smaller than ½ does not change the definition.
- Communication complexity, property testing, PCP-theorems and inapproximability of NP-hard problemsImagine Alice holds a string x and Bob holds a string y of equal length n. They want to figure out whether x = y. We show that in every communication protocol for this problem, there exist x and y for which Alice and Bob communicate at least n bits. The field of communication complexity gives many more results about such problems. We consider also non-deterministic classes.
- CryptographyWe define one-way function and RSA cryptography.
- Circuit complexity and parallel algorithmsIn computational complexity, there are several classes that represent problems for which highly efficient parallel algorithms exist. They are given by NC1 , NC2 , … and AC1 , AC2 , … Famous problems in this class are exponentiation and multiplication of matrices. If time permits, we study a few more problems. Finally we study problems that are P-complete, i.e., for which it seems currently unlikely that efficient parallel algorithms will be found.
- Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712
- Du, D., & Ko, K.-I. (2014). Theory of Computational Complexity (Vol. Second edition). Hoboken, New Jersey: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=784130
- Katz, J., & Lindell, Y. (2014). Introduction to Modern Cryptography (Vol. Second edition). Boca Raton, FL: Chapman and Hall/CRC. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=nlebk&AN=1766746
- Roughgarden, T. (2015). Communication Complexity (for Algorithm Designers). Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1509.06257