Syllabus
CSCI 6420
Computability and Complexity
Section 001
Spring 2006

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.

Beginning in the 1960s, emphasis 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 impossibility 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. 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. Functions and languages. Computability and partial computability. Diagonalization. Reductions and completeness. Examples of uncomputable problems.

2. Introduction to complexity. Complexity classes. Diagonalization over complexity classes.

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

4. Applications of complexity results. Cryptography. Digital signatures. Pseudo-random number generators. Communication protocols. 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. Excuses that you did not know about something because you did not come to class and did not obtain the information will not count for anything at all.

Those who choose not to attend class can count on doing poorly in this course. If you choose not to attend class, then you must live with the consequences of that decision, however bad they are.

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 and three exams. Cutoffs for grades will tentatively by 90% for an A, 80% for a B, 70% for a C and 60% for a D. Those cutoffs will not be raised.

Weather emergencies

In the event of a weather emergency, information about ECU can be accessed through the following sources:

ECU emergency notices	http://www.ecu.edu/alert
ECU emergency information hotline	252-328-0062

Students with disabilities

East Carolina University seeks to comply fully with the Americans with Disabilities Act. Students requesting accommodations based on a covered disability must go to the Department for Disability Support Services, located in Slay 138, to verify the disability before any accommodations can occur. The telephone number is 252-737-1016.