The course stresses methods for formal reasoning and modeling of general computation. The emphasis will be on written problem sets containing challenging problems. The key techniques to be learned are those of simulation of one computational model by another, reduction of one problem to another, and methods for classifying problem complexity.

The prerequisite material needed from CSc 473 is represented by Chapters 0-2 of the text used there: Michael Sipser, Introduction to the Theory of Computation, Boston: PWS Publishing Co., 1997. It is assumed you are familiar with the following topics: strings and sets (languages), DFAs, PDAs, regular sets, CFLs, nondeterminism, definitions of machine acceptance and the language accepted by a machine, the connection between types of grammars and types of machines, operations on languages such as union and star closure, and closure properties of the regular sets and CFLs.

• Required: Steven Homer and Alan L. Selman, Computability and Complexity Theory, Springer Verlag NY, 2001. (Clothbound, ISBN 0-387-95055-9). $49.95.
• A list of errata is available on the web. Obtain a copy and mark corrections in your text.
• There are locally discovered errata also

For Everybody: All students are required to fill out the web page entitled Computer Account Application Request Form at URL www.cs.arizona.edu/~apply. Do so whether or not you already have an account, and whether you are a Computer Science major or not. (This updates a Department database with your course selections, and you can be assigned a correct Computer Science ID (CSID) number). NOTE: If you have not done this update by Census Day (Wed 2 Feb), your account will be closed.

Here is how to proceed:

For a student with a currently active account in C SC: At the web page, under TYPE of APPLICATION, select UPDATE an OPEN account for new classes. Read the Appropriate Use Guidelines at www.cs.arizona.edu/terms.html before pushing ACCEPT.

For a student without a currently active account in C SC: To obtain a new account on the Department's instructional processor lectura, or to re-activate an existing account, use any machine to go to URL www.cs.arizona.edu/~apply. (During the first week of classes, the Department provides machines for this purpose in Room 737 Gould-Simpson Bldg.) At the web page, under TYPE of APPLICATION, select either NEW account on CS systems, or RE-activate an EXISTING closed CS account. Read the Appropriate Use Guidelines at www.cs.arizona.edu/terms.html before pushing ACCEPT.

Your registration information will be verified within a few minutes, and an account will be created for you, along with a keycard allowing round-the-clock lab access. The keycard will be available in Room 737 while the account registration machines are set up there, and at the Reception Desk in Room 917 thereafter. (Note that the Reception Desk has moved to the 9th floor along with the Department Business Office.)

For Everybody: You will need to know your CSID. To find your CSID at any time, log on to lectura under the name csid with password CSID. At the prompt, enter your Student ID (SID). Hyphens are optional. Record your CSID for future reference; grades will be posted using your CSID.

Each graded item, such as a homework or examination, is first awarded a raw score; raw scores vary with the number of questions, their difficulty, and their length. For each graded item, the raw score is normalized to a ``traditional'' scale in which 90 - 100 is an A, 80 - 89 is a B and 70 - 79 is a C. For each graded item, only the normalized score is recorded. The final cumulative course grade is computed as a weighted average of these normalized scores, using the weights described under Course Format above. The resulting weighted average is then converted to a letter grade using the ``traditional'' scale. Decisions on whether borderline scores (such as 89) will be recorded as the next highest letter grade will be made using (a) performance on the final examination and (b) evidence of accomplishment in the subject that is cumulative over the term.

Attendance is not enforced, but you are responsible for all material covered in lecture or assigned as reading. Arriving late to class is rude and disruptive; if you cannot arrive on time, don't bother to come.

Without prior arrangements, missed exams result in a grade of zero. Homework is due at the start of class on the due date; late homework is not accepted.

It is assumed that: you have the prerequisites for this course, and their prerequisites, etc., recursively.

The instructor reserves the right to fail for the course any student failing the final comprehensive examination.

The content of this syllabus is subject to change at the discretion of the instructor.

Assignments in this course require individual attention and effort to be of any benefit. All work is expected to be that of each student alone, without consultation with others, without reference to borrowed solutions and not the product of team efforts or collaboration with other authors. Plagiarism is the incorporation of someone else's words or ideas without proper attribution, whether taken from another student, an author, the instructor's published solutions or the Internet. Plagiarism constitutes theft of intellectual property, and those who engage in it will receive the failing grade of ``E''. These and other provisions are governed by the University's Code of Academic Integrity which applies to all those in this course. It is a violation of the Code to use another person's solutions as your own, whether those solutions are taken from a student in this course, or taken from solutions obtained from an earlier offering of this course, or taken from the files of a student who took this course earlier.

All written work submitted for credit must be prepared using a program capable of producing typeset output with the appropriate type faces, symbols and notation used in the theory of computation (e.g., TeX, LaTeX, troff, Microsoft Word + Equation). Do not submit handwritten work. Diagrams should be prepared with drawing tools like xfig, picasso, PowerPoint, etc.

Start each solution on a new page, repeat the problem statement, and number each page. Write on one side of the paper only. Submit answers in the labeled manila envelope (provided in class) on or before the due date. Do not seal the envelope (in order that it may be reused.) Write concise and limpid solutions, as failure to communicate clearly will cost points whether or not the conclusion is correct. It is highly advisable to revise your work before submission, and to consider whether your argument will be understandable to the reader. It is never a waste of effort to explain the strategy of what you intend to do in a proof or construction, before beginning the work in detail.

Students with disabilities, who may require academic adjustments or reasonable accommodations in order to participate fully in course activities or to meet course requirements, must first register with the Disability Resource Center, 1540 E 2nd St, 621-3268, email drc@w3.arizona.edu, URL http://drc.arizona.edu. DRC staff will qualify students for services, and provide a letter to the instructor listing accommodations to be made. This letter should be submitted by the student directly to the instructor as soon as possible during the first week of classes. The student should meet as soon as possible with the instructor by appointment or during office hours to discuss accommodations and how course requirements and activities may impact your ability to fully participate.

1. Introduction. History. Mathematical Preliminaries. The Search for Computability. What is Not Computable? Computational Models. Computational Complexity.
2. Computability. Turing Machines. Extensions and Restrictions of the Standard Model. Nondeterminism and Determinism. Random Access Machines. Universal Turing Machines. Diagonalization. Decidable and Undecidable Languages. Rice's Theorem. Recursion Theorem. Reducibility and Unsolvability. Functions Computed by Turing Machines: Partial and Total Computable Functions. Arithmetization of TMs. Partial Computable Functions and TM-computable Functions. Church's Thesis.
3. Complexity Classes. Measures of complexity: TIME, SPACE, others. Languages and Problems. Asymptotic orderings. Resource Bounds. RAM and TM Models. Time and Space-bounded complexity classes. Constructible Functions. Tape reduction for SPACE. Time compression theorem. Tape reduction for TIME. Relations between TIME and SPACE. Savitch's Theorem. Class Inclusions: What We Know. The DSPACE and DTIME hierarchy. Padding Lemmas. Extended Church's Thesis: TIME is poly related on all models; SPACE is linearly related on all models.
4. Intractability. Reductions. Hard and Complete Problems. NP-Complete Problems. Cook's Theorem: SAT is logspace-complete in NP. Reductions. The polynomial time hierarchy PH. PSPACE-Complete Problems. Provably intractable problems.
5. Circuit Complexity. Straight-Line Programs and Circuits. Normal-Form Expansions of Boolean Functions. Reduction Between Functions. The Circuit Model of Computation. Measures. Circuit Complexity Classes. Relationships Among Complexity Measures. Complexity of Boolean Functions. Upper Bounds on Circuit Size. Lower-Bound Methods.

Go to the URL http://www.library.arizona.edu/libresources/reserves.html to locate lists of (non-electronic, ``traditional'') reserve materials.

• http://www.cs.arizona.edu/classes/cs573/spring05/ is the URL for this document. It will be kept updated with information on assignments and exams. Reload it to see any changes.

When lecture slides are available, PDF versions are placed here.

• Lecture 01: Introduction
• Lecture 02: History: The Dreams of Reason
• Lecture 03: Turing Machines
• Lecture 04: Unsolvability
• Lecture 05: Reduction
• Lecture 06: Recursive Function Theory
• Lecture 07: Rice's Theorem
• Lecture 08: Relative Decidability
• Lecture 09: The Church-Turing Thesis (in PowerPoint, since conversion to PDF failed)
• Lecture 10: Complexity Classes
• Lecture 11: The TIME Hierarchy; Savitch's Theorem
• Lecture 12: Reducibility and Completeness

• Reading:
  • due 19 Jan: Homer & Selman, Chapter 1, Sec 1.1-1.6
  • due 31 Jan: Homer & Selman, Chapter 2, all
  • due 14 Feb: Homer & Selman, Chapter 3, all
  • due 21 Mar: Homer & Selman, Chapter 4, all
  • due 4 Apr: Homer & Selman, Chapter 5, Sec 5.1-5.5
  • due 11 Apr: Homer & Selman, Chapter 5, Sec 5.6-5.8
  • due 18 Apr: Homer & Selman, Chapter 6
  • due 27 Apr: Homer & Selman, Chapter 7
• Homework:
  • Homework 1 (due 2 Feb)
  • Homework 2 (due 16 Feb)
  • Homework 3 (postponed to 7 Mar)
  • Homework 4 (due 30 Mar)
  • Homework 5 (postponed to 20 Apr)
  • Homework 6 (optional, due 4 May)
• Midterm Examination:
  Postponed to after Spring Recess: Monday, March 21, in class. See Sample Midterm Examination
  See Midterm Topics
• Final Examination:
  Friday, May 13, from 11:00 am to 1:00 pm in Gould-Simpson 701.
  See Final Examination: Format & Topics

Exam grades are posted here and outside Room 739 Gould-Simpson. Grades are posted by the last six digits of your "Computer Science ID" (CSID).

• Homework, Final Exam & Course Grades