Computational Complexity

COT6410


Term: Spring 2011
Time: Tue Thu 1:30pm - 2:45pm
Location: HEC 0103

Instructor: Dr. Pawel Wocjan
Office hours: Tue Thu 3:00pm - 4:15pm
Phone: (407) 823-2844

Syllabus

Prerequisites:
COT 5405 "Design and Analysis of Algorithms".

Topics to be covered:
We will cover Chapters 1 - 4 and Section 5.2 Optimal Search Algorithms for NP.

We will also cover probabilistically checkable proof systems and their relation to the study of the complexity of approximation algorithms (Section 9.3 Probabilistically Checkable Proof Systems of the book "Computational Complexity - A Conceptual Perspective" by Oded Goldreich, Cambridge University Press, 2008).

Books:
The required book is "P, NP, and NP-Completeness - The Basics of Computation Complexity" by Oded Goldreich (Cambridge University Press, 2010).

Grading Policy:
The final grade will be determined as follows: 10% homework, 25% first midterm exam, 25% second midterm exam, 40% final exam.

I will give you homework assignments approximately every two weeks. I will present detailed solutions for the homework assignments in class and/or post the solutions on the course web page. The problems on the exams will be similar in nature to those on the homework assignments.

First midterm exam: Presentations

Second midterm exam: Take-home exam due on 04/07

Final exam: 04/26 (Tuesday) 1:00pm - 3:50pm This is the official date/time for the final exam as specified by the UCF Spring 2011 Final Exam Schedule. You may not take the final exam on a different day/during a different time.

The grades are A/B/C/D/F. You may also receive +/-.

I will return the exams and homework assignments in class or you may pick them up during my office hours.

Academic Integrity:
Plagiarism and cheating of any kind on an examination or assignment will result at least in an "F" for that assignment (and can, depending on the severity of the case, lead to an "F" for the entire course) and may be subject to appropriate referral to the Office of Student Conduct for further action. See the UCF Golden Rule for further information. I will assume for this course that you will adhere to the academic creed of this University and will maintain the highest standards of academic integrity. In other words, do not cheat by giving answers to others or taking them from anyone else. I will also adhere to the highest standards of academic integrity, so please do not ask me to change (or expect me to change) your grade illegitimately or to bend or break rules for one person that will not apply to everyone.

Announcements

TBA

Lectures

The following is a list of topics covered in each lecture, together with pointers to the corresponding portions of the text and, where appropriate, additional lecture notes.

  Topic
Lecture #1 (01/11) Syllabus
Introduction
Representation
Computational task, search problems, decision problems
Lecture #2 (01/13) Uniform models, algorithms, Turing machines
Lecture #3 (01/18) Uncomputable functions, the Halting problem
Lecture #4 (01/20) Universal machines, Kolmogorov complexity
Lecture #5 (01/25) Reduction of the Halting Problem to the Modified Post Correspondence Problem
Lecture #6 (01/27) Example of the resulting tiles for a simple Turing machine
Reduction of MPCP to PCP
Lecture #7 (02/01) The Cobham-Edmonds thesis/Strong Church-Turing thesis
Universal machines
Space complexity
Oracle machines and Turing reductions
Lecture #8 (02/03) Search version: finding vs checking, PF, PC
Decision version: proving vs verifying, P, NP, proof system
Lecture #9 (02/08) Equivalence of the search and decision versions of NP
Lecture #10 (02/10) Traditional definition of NP in terms of non-deterministic Turing machines
Equivalence of the definitions based on non-deterministic Turing machines and verification procedures
Lecture #11 (02/15) Solutions for problems on HW1
Lecture #12 (02/17) Definition of oracle TM
Turing reduction
Cook reduction
Karp reduction
Levin reduction
Lecture #13 (02/22) Reducing optimization problems to search problems
Lecture #14 (02/24) Implicit decision problems
Self-reducibility
Lecture #15 (03/01) Overview to NP-completeness
Definitions of NP-complete/hard
Lecture #16 (03/03) Class canceled
Lecture #17 (03/15) Topics for presentations
Lecture #18 (03/17) Guidelines for Ex. 4.18
Lecture #19 (03/22) Discussion of solutions for HW 2
Lecture #20 (03/24) Proof of existence of NP-complete problems
Lecture #21 (03/29) Proof of NP-completeness of CSAT and SAT

Homeworks


Dates/topic for presentations

1. (04/05) Set Cover, Exact Cover, 3-Exact Cover (Kalyanic, Julin)
2. (04/05) Vertex Cover, Independent Set, Clique ( Juyao, Chuan)
3. (04/07) Graph 3-Colorability (Amerah, Sana, Enas)
4. (04/07) Reduction (Search -> Decision; Graph Isomorphism; 3-Colorability) (Amy, Steven)
5. (04/12) Integer Linear Programming (Yuyan Bao, Qianpiu Xiao)
6. (04/12) 2D Bin Packing (Sarah, Steven)
7. (04/14) Subset Sum Problem (Jonathan, Omar)
8. (04/14) Jigsaw Puzzle (Satej)