Syllabus
CSCI 6420
Computability and Complexity
Sections 001 and 601
Spring 2016

Contents

---

1. Prerequisites
2. Introduction
3. Course objectives
4. Topics
5. Attendance policy
6. Incompletes
7. Grading
8. Distance education
9. Lecture schedule and reading assignments
10. Additional information

Prerequisites

You should be proficient at writing computer programs in some language. We will not write programs for this course, except in rough pseudo-code. But it is important that you understand how that pseudo-code can be translated to a working computer program, and that you have a grasp of how some of the details that are left unstated in the pseudo-code can be fleshed out in a real program.

Introduction

The study of the theory of computing began in the 1930s with the work of Turing and Gödel, and has continued since then through the work of researchers too numerous to name. Early researchers primarily asked what could be computed if resources such as time and memory were unbounded, and how the computability of one problem related to the computability of another problem. Some computational problems that you might initially think are relatively straightforward were shown to be unsolvable. Results from this theory of computability have some important practical significance, but some of them are rather esoteric for the practicing computer scientist.

Mainly beginning in the 1960s, emphasis among computer scientists shifted from unbounded resources to cases where the available resources were bounded by some function of the size of the problem. Results having to do with bounded-resource computation generally fall under the heading of complexity theory. It was found that some of the methods of computability theory applied quite nicely to complexity theory, while others did not seem to travel well. Complexity theory has matured over time and is now a cornerstone of computer science, where its results are of greater significance to the practicing computer scientist than those of computability theory. Knowledge of the basic results of complexity theory are now recognized as part of the core of computer science.

Before the mid 1970s, most of the more important results of both computability and complexity theory were impossibility results. They stated that certain problems could not be solved, or could not be solved within given resource constraints. Beginning in the 1970s, and continuing through the present day, there have been some remarkable results that show how the difficulty of solving one problem can be turned into the possibility of solving another. Techniques have been developed that are so subtle, they solve problems that you would initially conclude could not possibly be solved.

This course will explore important results in the theory of computing. You will be expected to do proofs relating to the material covered. We will hit the high points of computability theory, then study the basics of complexity theory, and then examine how complexity theory makes tools available to the working software designer.

Course objectives

The student should gain a better appreciation for what can be computed, and be able to recognize well-known difficult problems. Students should be familiar with standard terminology and notation and know definitions of terms. He or she should be able to carry out elementary proofs showing that problems are difficult to solve. The student should also be able to apply standard results of the theory of computation to his or her work, and be able to understand the significance of important new results as they come out.

Topics

1. Strings, sets, languages and functions. Notation and terminolgy.

2. Computability. Diagonalization. Examples of uncomputable problems.

3. Introduction to complexity. Complexity classes.

4. Polynomial time complexity. Deterministic and nondeterministic computation. The classes P and NP. NP-completeness. Examples of NP-complete problems.

5. Other complexity classes. The class PSPACE and PSPACE-completeness.

6. Applications of complexity results. Cryptography. Interactive and zero-knowledge proofs.

Attendance policy

I will not take attendance. It is up to you to attend class. You are responsible for announcements and assignments given in class. If you miss a class, it is up to you to obtain notes and any other information that was provided in the class.

Incompletes

No incompletes will be issued in this course except for extraordinary circumstances, and even then only if you are nearly done already, and have done work of acceptable quality that it is realistic that you can pass the course.

Grading

Grading will be on the basis of homework (25%), 4 midterm exams (12% each) and a comprehensive final exam (27%). The exam schedule is as follows.

Tentative cutoffs for grades are as follows. These cutoffs will not be raised.

Distance education

---

This course is taught both face-to-face and online. We will be in a classroom that have video capabilities, so that you can see the lectures. I will put up material on a screen. All of the material is available to you as the class notes.

Email is the best way to ask questions outside of class. I will try to reply as quickly as possible. I don't do well with telephones or skype or any of those things. There is something about them that does bad things to my psyche. I have always been this way. Some people are afraid of elevators. I am bothered by telephones.

This is my first time teaching online. I expect to learn it as I go. I would appreciate comments and recommendations from you as we go about how to improve it.

Exam Information for Online Students

If you are taking the course online, you are allowed to come to class and take the exam in person. If you choose not to do that, you must have a proctor for all exams. You must use the University of North Carolina Proctoring Network. See http://online.northcarolina.edu/exams/overview.htm.

Lecture schedule and reading assignments

The following schedule lists brief topics along with sections from the book and notes that cover them. You should read the relevant sections of the book and notes before the class.

This outline is both approximate and tentative. It will probably need to be adjusted.

Additional information

For information about

• student conduct
• students with disabilities
• weather emergencies