Spring 2006

**You may bring two 8.5 by 11 inch sheets of paper to the exam with
your notes on them. You may write on both sides.**

In addition to the material listed on the review sheets for Exams 1 and 2, review the following:

- Lectures since March 28.
- Readings:
- Ch 9 (skip sec 9.4 and sec 9.5)
- Ch 10. Read it all except:
- skim sec 10.1.2
- skip sec 10.2.2 and sec 10.2.3 (just remember that SAT is NP-complete),
- skip sec 10.3.2 (just remember that CSAT is NP-complete)
- skip sec 10.3.3 (just remember that 3SAT is NP-complete)
- skip sec 10.4.4 (just remember that HC is NP-complete)
- skip sec 10.4.5 but do read the part on p. 461 about TSP

- Quizzes 10-12 and their solutions (given in class)
- Homework assignment 6 and its solutions (provided in class)

The format of the exam will be some short answers and some "work-out" problems. Difficulty will be in between the quizzes and the homework. Here are some suggestions for things to know:

- definitions of
*decision problem*,*decidable*and*undecidable* -
*Church-Turing thesis*: TMs can compute anything we would think of as being computable - know in principle how to encode a TM as a binary string (details
are not important); this implies that all TMs can be listed
(in an infinite list)
- definition of L_d, the
*diagonalization*language; how to show it is not r.e. - recursive languages are closed under complement
- if L and its complement are both r.e., then both are recursive
- definition of L_u, the
*universal*language; how to show it is r.e. but not recursive - definition of the
*halting problem*; how to show it is r.e. but not recursive - definition of problem P1
*reducing*to problem P2 and the implications thereof regarding decidability (and "r.e."-ness) of the two problems - definition of a
*nontrivial property*of the r.e. languages; statement (but not proof) of Rice's theorem; how to use Rice's theorem to prove that certain languages are not recursive - Definitions of time complexity for deterministic and non-deterministic
Turing machines, big-oh notation,
polynomial time for DTMs and NTMs, the sets P and NP.
- Why it is reasonable to think of P as the "tractable" problems.
- Why the question whether P equals NP is of practical importance.
- Definition of polynomial time reduction and its implications.
- Definition of NP-complete and its implications.
- Definitions of TSP, HC, SAT, CSAT, 3SAT, IS, NC (also called VC
for vertex cover).
- Statement of Cook's theorem.
- Know the two ways to show a problem is NP-complete: directly
with brute force vs. using a reduction. For reductions,
*be sure to get the direction correct!*

- Show a problem is not recursive or not r.e. using a reduction
- Show a problem is NP-complete using a reduction.
- Given a language, figure out how to classify it (regular, context-free, recursive, r.e., not r.e.) and prove it. For instance, if you decide a language is context-free but not regular, you could, for example, show a context-free grammar for the language and use the pumping lemma for regular languages to show that it is not regular.