 |
Final Exam Study Guide, Math 421, Fall 2019
More content and corrections may be added to this page.
|
Examinable Material (Course Coverage) |
- The three handouts to supplement the textbook:
- Self-Referencing, Uncountability
and Uncomputability in CPSC 421;
-
this article on the Myhill-Nerode theorem;
-
notes on sneaky complete languages.
-
Sipser's Textbook:
-
Chapter 1, excluding the Pumping Lemma in 1.4.
-
All of 3.1, the part of 3.2 on multi-tape and non-deterministic Turing
machines.
-
All of 4.2.
-
The part of Chapter 5 about reducing an undecidable language
to another language, L, to show that L is also undecidable (see notes
from 10_21 and 10_23).
-
All Chapter 7, except the definition of NP as a polynomial time verifiable
language; we defined NP only as a language decidable by a non-deterministic
T.m. in polynomial time.
-
All of 8.1 and 8.2.
-
9.2: Oracle machines: notation, (e.g., P^A = poly time with oracle A)
and basic properties. co-NP, P^SAT.
Theorem: P^B = NP^B for any PSPACE-complete problem, B
(second half of Theorem 9.20, the Baker-Gill-Solovay Theorem), including
the "one line" proof: P^B ⊂ NP^B ⊂ NPSPACE ⊂ PSPACE ⊂ P^B .
-
Remarks and additional material:
- We introducted SNEAKY-NTM = { < M,w,1^t > | M accepts w within
time t } which is NP-complete.
An analogously defined SNEAKY-PSPACE = { < M,w,1^s > | M accepts w within
space s } is PSPACE-complete.
(Hence we know a PSPACE-complete language even though we did not
cover Section 8.3.)
|
|---|
|
Practice Problems for the Final Exam |
All homework problems and the problems on the midterm are good practice
problems.
Below I list the problems that directly correspond to the material
learned this year in the language that we used.
Here are some problems for which I will provide partial or full solutions:
Here are some problems with some brief solutions:
- Final 2004, Problems 1,2,5,6,7,8,9.
For 9(b) the hint--in the terminology we used this year--is to use the
Myhill-Nerode
theorem.
(solutions).
Here are some problems for which I will not provide solutions:
- Midterm 2007, Problems 1,2.
- Midterm 2009, Problems 1,2.
- Final 2009, Problems 1,3,4.
- Final 2010, Problems 1,2,4.
- Final 2011, Problems 1,2,4,5,8.
- Final 2014, Problems 1,2,4,5(a)-(d)
(in Problem 2, Future(L,0001) means AccFut_L(0001); the language NP-easy in
5(d) is what we called NP-SNEAKY this year).
Some problems from the Final 2017 were discussed on 11_29.
|
|---|
|