CSc 85040
Topics in Computational Complexity: Foundations of Computational Complexity Theory
Code: 94280
3 credits
Wednesdays 2:00 - 4:00 pm
Room TBA

Professor Noson Yanofsky
Office 1430N, Brooklyn College.
 

This is a general introduction to complexity theory, the study of the “efficiency” and “hardness” of solvable computational problems. We shall look at different models of computation, different measures of efficiency (e.g. time, space etc). We shall study the relationship of complexity theory to logic. Abstract complexity theory will also be discussed.

Texts: 
Required:  Computational Complexity by C.H. Papadimitriou [Pap]

Recommended:

            Introduction to the Theory of Computation, Second Edition by M. Sipser [Sipser]

Also Used:    

            Computability : An Introduction to Recursive Function Theory By N.J. Cutland [Cutland]

            Computability, Complexity and Languages, Second Edition by M.D. Davis, R. Sigal, E.J. Weyuker [Davis et al] 

            A Catalog of Complexity Classes by D.S. Johnson in Handbook of Theoretical Computer Science (HTCS) [Johnson]

            Handbook of Theoretical Computer Science, Volume A. [HTCS]       

            There will also be handouts.             

All these books and papers will be on reserve in the library.

 
Tentative Schedule:

1) Review Basic Complexity Theory

·        Turing Machine, P, NP, Co-NP

·        Polynomial Reduction, NP-Complete

·        SAT, Cook-Levin theorem

·        [Pap, 1,2,3,7,9], [Sipser,7], [Davis et al, 15]

2) Polynomial Space Complexity

·        PSPACE

·        Savitch’s Theorem

·        PSPACE-Complete problems

·        [Pap, 19], [Sipser, 8.1,8.2,8.3]

3) Logarithmic Space

·        L, NL

·        NL-Completeness

·        Immerman-Szelepcsenyi Theorem

·        [Pap, 16], [Sipser, 8.4,8.5,8.6]

4) Probabilistic / Random Computation

·        Probabilistic Turing Machines

·        Primality

·        BPP, ZPP

·        [Pap, 11], [Sipser, 10.2]

5) Parallel Computation

·        CREW, PRAM models

·        NC

·        [Pap, 15], [Sipser 10.5]

6) Polynomial Hierarchy

·        S, D, P

·        [Pap, 17], [Sipser 9.1]

7) Descriptive Complexity Theory

·        Fagin’s Theorem

·        Logic and the Polynomial Hierarchy

·        [Pap, 8.3]

8) Abstract Complexity Theory

·        Blum’s Axioms

·        Gap Theorem

·        Speedup Theorem

·        [Cutland, 12], [Davis et al,14], [HTCS, 3]