| Class meeting | MWF 10:00–10:50pm, Rawl 202 | ||
|---|---|---|---|
| Instructor | Karl Abrahamson | ||
| Office | Science and Technology C-113 | ||
| Office hours |
|
||
| Phone | 328-9689 | ||
| abrahamsonk@ecu.edu | |||
| Course web page | www.cs.ecu.edu/~karl/6420/spr13/ | ||
| My web page | www.cs.ecu.edu/~karl/ | ||
| Text | Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. |
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.
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 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.
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.
Strings, sets, languages and functions. Notation and terminolgy.
Computability. Diagonalization. Examples of uncomputable problems.
Introduction to complexity. Complexity classes. Diagonalization over complexity classes.
Polynomial time complexity. Deterministic and nondeterministic computation. The classes P and NP. NP-completeness. Examples of NP-complete problems.
Other complexity classes. The class PSPACE and PSPACE-completeness.
Applications of complexity results. Cryptography. Digital signatures. Pseudo-random number generators. Communication protocols. Interactive and zero-knowledge proofs.
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 will be on the basis of homework, midterm exams and a comprehensive final exam. There will be four midterm exams, on February 11, March 4, April 1 and April 22. The final exam will be Monday, May 6 from 8:00am to 10:30am in the regular classroom.
Tentative cutoffs for grades will tentatively be as follows. These cutoffs will not be raised.
| A | 90% | |
| B | 80% | |
| C | 70% |
For information about