Requirements for Exam in ACC
List of all definitions, theorems and important examples you are expected to know at the exam.
Computer architecture
Representation of data in computer memory
Machine instructions
Relationship between high-level languages and the machine
Functions provided by operating systems
Memory management
Caching
Models of computation
Notation for strings
Problems, languages and encoding
Turing machine, configuration, computation
Variants of the Turing machine: one-way-infinite, multi-tape, randomized, with oracle, interactive
Random Access Machine
Equivalence of TM and RAM
Computability
(Partial) computability of functions and languages
Language is partially computable iff it is enumerable.
Encoding of machines, universal language Lu, Universal Turing Machine
Lu is partially computable, but not computable. Its complement is not partially computable.
Post's theorem
Operations on machine codes
Many-to-one reduction between languages
Rice's theorem (without proof)
Hardness and completeness of languages
Relative computability
Arithemtical hierarchy
Properties of the arithmetical hierarchy, connection to quantified formulas
Time complexity
Run time of a computation, time complexity of a machine
Asymptotic notation: O, Ω, Θ
1-tape TM requires quadratic time to recognize palindromes.
k-tape TM can be simulated by 1-tape TM with quadratic slowdown.
Classes DTIME(f), DTIMEF(f), P, and PF
Time-constructible functions
P and NP
Polynomial-time many-to-one reduction
SAT and Independent Set can be reduced to each other
Class NP (defined using certificates)
NP-hardness and NP-completeness
If K is reducible to L and L is in P, then K is in P.
If K is reducible to L and K is NP-hard, then L is NP-hard.
Cook-Levin theorem (SAT is NP-complete)
NP-completeness of 3-SAT, 3,3-SAT, 3D Matching, ZOE, 3-Coloring, Hamilton Path
Class co-NP
UNSAT and Tautology are co-NP-complete.
There exist oracles such that P[A]=NP[A] and P[B]≠NP[B].
Boolean circuits
Combinatorial and Boolean circuits
Computation of a circuit
Every Boolean function can be computed by a Boolean circuit
Circuit families and uniformity
Languages in P have polynomial-size uniform families of circuits
Circuit-SAT is NP-complete
Circuit-SAT reduces to SAT (proves the Cook-Levin theorem)
Non-determinism
Non-deterministic Turing Machine
Classes NTIME(f), NTIMEF(f)
NP = NTIME(poly(n))
Space complexity
Input, output, and work tapes
Space used by a computation, space complexity of a machine
Classes DSPACE(f), NSPACE(f), DSPACEF(f), NSPACEF(f), PSPACE, NPSPACE
Space-constructible functions
Basic inclusions: DTIME(f) ⊆ NTIME(f) ⊆ DSPACE(f) ⊆ NSPACE(f)
P ⊆ NP ⊆ PSPACE ⊆ NPSPACE
DSPACE(f) ⊆ DTIME(exp(O(f))) for every f ≥ log n
PSPACE ⊆ EXPTIME
Configuration graph of a NTM
Bounds on complexity of reachability imply relationship between complexity classes.
NSPACE(f) ⊆ DTIME(exp(O(f))) for every f ≥ log n
Reachability is in DSPACE(log2 n).
Composition of space-bounded functions
Savitch's theorem: NSPACE(f) ⊆ DSPACE(f2).
PSPACE = NPSPACE
Immermann-Szelepcényi theorem: NSPACE(s) = co-NSPACE(s)
Polynomial space
Quantified Boolean Formula problem
QBF is PSPACE-complete
Strategies for 2-player games with complete information are in PSPACE.
Alternating Turing Machine
Classes ATIME(f) and AP
AP = PSPACE
Polynomial hierarchy
Problems Σk-SAT and Πk-SAT
Polynomial hierarchy: classes ΣkP and ΠkP, class PH
Inclusions between classes of the PH
Equivalent definition using oracles
Collapse of the PH
Inside P
Log-space reduction
Classes L and NL
Circuit evaluation is P-complete.
Reachability is NL-complete.
2-SAT is NL-complete.
Hierarchy theorems
Space hierarchy theorem
Time hierarchy theorem
Circuit complexity
Circuit size, classes SIZE(f)
Every Boolean function with n inputs can be computed by a circuit of size O(2n*n).
There are functions which require circuits of size 2n/10n.
Computation with advice, classes DTIME(f)/g and P/poly
For every k>0, there is a language in EXP SIZE(nk + k).
EEXP is not a subset of P/poly.
If NP ⊆ P/poly, then PH = Σ2P (without proof).
Probabilistic computation
Probabilistic TM
Classes BPP, RP, co-RP, ZPP
Amplification of probability of success
Certificate-based definitions of probabilistic classes
ZPP = RP ∩ co-NP
P ⊆ ZPP ⊆ (co-)RP ⊆ BPP, RP ⊆ NP, BPP ⊆ PSPACE
BPP ⊆ P/poly
Regular languages
Deterministic Finite-state Automaton
Computation, acceptance, extended transition function
Regular languages
{ 0n1n } is not regular.
Pumping lemma for regular languages
Product automaton
Intersection of regular languages is regular.
Non-deterministic Finite-state Automaton
Languages accepted by NFAs are regular.
NFA with ε-transitions
Every ε-NFA can be reduced to a NFA
Operations on languages
Regular languages are closed on ∩, ∪, complement, concatenation, iteration, reversal.
Kleene's theorem
Bi-directional DFA (as a restricted TM)
DSPACE(1) is the class of all regular languages.
Fine-grained complexity
Fine-grained reductions
Orthogonal Vectors problem, the OV Hypothesis
(Strong) Exponential Time Hypothesis
OVH implies lower bound of NFA acceptance.
ETH implies lower bound for dominating set.
SETH implies OVH.
OVH implies lower bound for Longest Common Subsequence (without proof).