COMP4141 Theory of Computation
Course recap
Paul Hunter
CSE, UNSW
April 21, 2021
Final exam
Final exam:
Wednesday, May 12
Available 10am AEST
Due: Thursday, May 13, 10am AEST
Submission via give: multiple submissions ok - last one before
due date counts
Lateness: 25% per 15 minutes or part thereof.
Worth 50% of overall grade. Must achieve 40% to pass
course.
Final exam
10 questions:
6 questions on Week 1-5 content;
4 questions on Week 7-10 content
Proof-based questions (as with Assignments 1,2, 3b, 4)
Assessment based on understanding and ability
Any passive (i.e. existing) material acceptable – properly
referenced
Any material taken from active sources is in breach of Student
Conduct and will be subject to plagiarism review
Week 1 recap
Formal languages
Alphabets, Strings/words, Languages
Recursive definitions
Deterministic Finite Automata (DFA)
(Q,Σ, δ, q0,F )
L(A)
Non-deterministic Finite Automata (NFA)
Non-determinism
-transitions
Equivalence of DFAs and NFAs
Subset construction
Week 2 recap
Regular expressions
Definition, L(R)
Equivalence to DFAs
Pumping Lemma
Myhill-Nerode theorem
Need to know
Regular expressions
Definition, L(R)
How to do proofs with them
Finding R or L such that L = L(R)
Pumping Lemma - how to use it, limitations
Myhill-Nerode theorem - how to use it, limitations
Week 3 recap
Context-free languages
Context-free grammars
Derivations, parse trees, ambiguity
Pushdown automata
Pumping lemma for CFLs
Closure properties of CFLs
Chomsky normal form
Non-emptiness and word acceptance algorithms
CKY algorithm
Chomsky hierarchy
Need to know
CFGs and PDAs: Definitions, how to use
Pumping lemma: How to use
Algorithms for CFLs
Grammars for
Type 3: Regular languages,
Type 2: CFLs, and
Type 0: Recursively enumerable languages.
Weeks 4 and 5 recap
Turing Machines, Recursive and Recursively Enumerable languages
Turing Machines
Definitions, accept vs decide
Variants: stay-put, semi-infinite tape, multi-tape,
non-determinism
Enumerators
Universal Turing Machine
Rec, RE, coRE
Rec = RE ∩ coRE
Encodings
Reductions: many-one vs Turing
Undecidable problems: ATM = {〈M,w〉 : M accepts w}
Rice’s theorem
Need to know
TMs: Definitions, how they work
Many-one reductions: Definitions, how to use
Oracles
Rice’s theorem: When it applies
Week 7 recap
Resource-bounded computation:
TIMEt(n)
NTIMEt(n)
SPACEt(n)
NSPACEt(n)
Time and Space-hierarchy theorems
P and NP
Need to know
How to use the Space/Time-hierarchy theorems
Class definitions and relation to other classes
How to do NP-completeness proofs
Week 8 recap
NP-completeness proofs
SAT (Cook’s theorem)
3SAT, 4SAT
Vertex Cover
Clique
Hamiltonian Path, Hamiltonian Cycle
Travelling Salesman
Subset Sum
Integer Linear Programming, 0-1 ILP
3COL
Need to know
Reduction strategies for NP-completeness proofs
Generalization
Problem restatement
Gadget construction
Week 9 recap
Complexity classes:
coNP, Validity
EXPTIME, Bounded Halt
PSPACE, QBF (QSAT)
L, NL, ≤L, Path
Complexity classes
P
NP
NP-c
coNP
PSPACE = NPSPACE
EXPTIME
NL = coNL
L
Complexity summary
Class Characterization Problem Notes
P
⋃
k∈NTIME(n
k) Horn-SAT
NP
⋃
k∈NNTIME(n
k) SAT, 3SAT Poly. verifiable
PSPACE
⋃
k∈N SPACE(n
k) QBF = NPSPACE
coNP Languages L such
that L ∈ NP
Validity Poly. refutable
EXPTIME
⋃
k∈NTIME(2
nk ) Bounded-halt 6= P
L SPACE(log n) Und. Path
NL NSPACE(log n) Path, 2SAT = coNL
Need to know
Class definitions and relation to other classes
Consequences of Savitch’s theorem
PSPACE-completeness proofs
How to do logspace reductions
Week 10 recap
Oracle machines
Alternation
Polynomial-time hierarchy
Probabilistic computation
Probabilistic Turing Machines
Probabilistic complexity classes: PP, BPP, RP, ZPP.
PΣ1P = NP Π1P = coNP
∆2P = P
NP = PcoNP
Σ2P = NP
NP Π2P = coNP
NP
P∆3P = P
Σ2P
Σ3P Π3P
...
PSPACE
Need to know
Oracle machines: Definition, how to use
Alternation: Definition, how to use
Probabilistic computation: Definition, how to use
Relation between Alternation complexity classes and classical
complexity classes
Probabilistic complexity classes: PP, BPP, RP, ZPP
























































































































































































学霸联盟