The final exam will be Monday, May 6 from 6:30pm to 7:45pm in Austin 304. Some additional practice questions are available.
Programs to do modular inversion, getting a prime number and factoring (using Pollard's algorithm) are available. They are written in Astarte. Use astr to run them. For example, astr inv will run the inv.ast program.
See the syllabus for a description of the course.
Office hours are MW 2:00-3:15pm and TTh 11-12:15pm or by appointment. My home page is www.cs.ecu.edu/~karl/.
[1/7/02] We went over fundamental mathematical notation and terminology, including sets, operations on sets and relations involving sets, functions and programs. Most of this is in Chapter 0 of the text.
[1/9/02] We began looking at computability. We defined computable functions and computable sets, and looked at some examples of computable functions and sets. We then turned to uncomputable sets. Our goal for the near future will be to prove that some sets are uncomputable. This material is in Chapter 4 of the text.
[1/14/02] We proved that the halting problem is undecidable using diagonalization. We proved that K is undecidable, and that another problem concerning the behavior of programs is also undecidable. This continues Chapter 4.
[1/16/02] We proved Rice's theorem. See the notes on Rice's theorem.
[1/21/02] Holiday.
[1/23/02] We went over homework, and introduced the notion of m-reduction. We looked at basic properties of m-reductions, and showed that the halting problem and the diagonal set K m-reduce to one another. We solved problem 3 of the homework by reduction instead of by diagonalization. This material is in Chapter 5 of the text.
We have skipped material in Chapter 4 on Turing-recognizable languages. We will come back to pick that up.
[1/28/02] We looked at examples of undecidable problems that are not directly asking questions about what programs do when you run them, including problems from mathematical logic and problems related to context-free grammars. Then we began looking at Post's correspondence problem.
[1/30/02] We proved that Post's Correspondence Problem is undecidable by reducing the halting problem to it. We defined partially computable sets and saw that the halting problem is partially computable.
[2/4/02] We looked at recursively enumerable sets, and proved that the class of recursively enumerable sets is exactly the same as the class of partially computable sets. We defined m-complete problems, and showed that the halting problem is m-complete.
[2/6/02] We discussed the homework and finished talking about m-complete problems. PCP is m-complete. At this point we are done looking at computability, and are ready to look at resource-bounded computation.
[2/11/02] We explored complexity classes. The time complexity of program p on input x is the number of steps performed by p when it is run on input x. The space complexity is the number of basic memory cells (such as tape cells on a Turing machine) that it uses. TIME(t(n)) is the class of all decision problems that are solvable in time at most c*t(n) for some constant c on inputs of length n, for all but finitely many n. SPACE(s(n)) is the class of all decision problems solveable in space at most c*s(n) for some constant c on inputs of length n, for all but finitely many n.
We defined honest functions, which are functions that are suitable as time or space bounds. The idea is that the cost of computing an honest function should not be more than the cost that the function indicates. You should be able to precompute the cost without blowing your whole budget on the cost computation. Honest functions are also called time-constructible (for time limits) or space-constructible (for space limits).
[2/13/02] We proved stated and proved the hierarchy theorems for time and space. See Section 9.1 of the text.
[2/28/02] We proved the gap theorem. It shows that the honesty condition in the hierarchy theorems are required. It also demonstrates how important it is to have proofs of theorems, since intuition can be wrong. We defined the class P of all decision problems solvable in polynomial time, and saw some examples of problems in P. Material on polynomial time computation is in Chapter 7 of the text.
[2/20/02] We defined nondeterministic computation and the class NP of decision problems computable nondeterministically in polynomial time. We defined polynomial time reductions and NP-complete problems. (A problem B is NP-complete if it is member of NP and every member of NP polynomial-time reduces to B.)
If P is not equal to NP and problem B is NP-complete then B cannot be in P. It is conjectured (but not known) that P is not equal to NP. This will be our basis for establishing evidence that some problems are not in P. This material is in Chapter 7 of the text.
[2/25/02] Midterm exam 1.
[2/27/02] We went over exam 1, and scheduled a retry for March 6.
[3/4/02] We reviewed the basic definitions of NP-completeness and introduced the satisfiability problem (SAT). SAT is NP-complete.
[3/6/02] Midterm 1A (retry of first midterm).
[3/11/02] Spring break.
[3/13/02] Spring break.
[3/18/02] We covered more material on NP-completeness. We defined CNF-SAT 3-SAT and sketched a proof that 3-SAT is NP-complete.
[3/20/02] We proved that the Vertex Cover problem is NP-complete by reducing 3-SAT to it. We also proved that the Independent Set problem is NP-complete.
[3/25/02] We showed that the Hamilton Path problem is NP-complete, and noted that variations on it are also NP-complete. We showed that the Traveling Salesman problem is NP-complete.
[3/27/02] We looked at more NP-complete problems. We showed that the subset sum problem is NP-complete. We showed that the subgraph isomorphism problem is NP-complete.
[4/1/02] We proved that the satisfiability problem is NP-complete.
[4/3/02] We talked about complexity classes outside of NP, including Co-NP, PSPACE and EXPTIME. We noted that PSPACE is the same as NPSPACE (nondeterministic polynomial space). Each of these classes has a natural notion of a complete problem, and each has examples of complete problems. The validity problem for propositional logic is Co-NP-complete. Determinining whether a position in generalized checker game is a winning position for one of the players is PSPACE-complete. ML type checking is EXPTIME-complete.
[4/8/02] We defined the TQBF problem and noted that it is PSPACE-complete. (We did not prove that. It requires a generic reduction.) We proved that the generalized geography problem is PSPACE-complete by showing that it is in PSPACE and by reducing TQBF to it.
[4/10/02] We went over mathematical prelimaries for looking at cryptography and other applications of complexity theory.
[4/15/02] We reviewed briefly for the test. We looked at telling whether a number is prime.
[4/17/02] Exam 2.