DM/DMP67: Complexity Theory

Week 5: The first lecture will be in the seminar room at 12:15 on February 2. There will be a general introduction to complexity theory, models of computation and complexity classes. The first "real" topic will be Turing machine complexity, and we will start with the first four sections of chapter 2 in Papadimitriou's textbook, some of which can be done very quickly or skipped since we all know what a TM is.
We will meet the first Friday, though not until 9:00. We will discuss Cook's theorem, with respect to Turing machines.
First problems: 2.8.4, 2.8.5. Note: I have postponed 2.8.12 until the next week, since I didn't cover as much as I expected in the first lecture.
Week 6: We will continue on chapter 2, starting with section 2.4. (We will also look at REACHABILITY from chapter 1.)
Problems for Friday, February 19:
Do 2.8.12, 2.8.16 and the first three parts of 7.4.12. For 7.4.12, I haven't been able to do part (d) within a reasonable amount of time. Can you? Read the last two parts, but let's not do them.
Week 7: We will cover chapter 7.
Problems for Friday, February 26: We will do the problems that should have been for February 19 and begin on 7.4.17. (There was an article handed out in connections with 7.4.17.)
Week 8: We did a padding argument, covered chapter 8, and covered Pratt's theorem from chapter 10.
Problems for Friday, March 5:
Whatever we don't finish from last week, plus 7.4.7 and 8.4.2.
Week 9: No class was held on Tuesday due to illness. On Friday, Lars did part c of 7.4.17 and Morten started on part d.
On Friday, March 12, we will finish off problem 7.4.17 and do 7.4.7 and 8.4.2.
Week 10: We covered the first two sections of chapter 11.
Problems for Friday, March 19: 10.4.6, the subsection of 11.1 on symbolic determinants, 11.5.14.
Week 11: We will finish chapter 11, skipping most of section 11.3. We will also cover Shannon's result showing that almost all functions on n variables require circuits of size at least (2^n)/n. This can be found in Wegener's book, starting on page 87.
Problems for Friday, March 26: 11.5.23, 11.5.24.b (note that a formula with k-1 variables can also be seen as a formula with k variables, so the advice that works for k variable formulas should also work for k-1 variable formulas).
The next two problems are from the monograph "Structural Complexity I", by Balcazar, Diaz and Gabarro.
Consider the class PF of functions which are computable in polynomial time. Show that P/PF = P.
A generator is a circuit G with m input gates and n output gates, computing a boolean function f from {0,1}^m to {0,1}^n, which has an extra output gate called "domain indicator". The output of G is considered undefined whenever the domain indicator outputs 0. In this way, G computes a partial function which coincides with f when the domain indicator is 1, and is undefined otherwise. We say that G generates the set A if and only if A is the range of this partial function. A subset A of {0,1}^* has polynomial size generators if for some polynomial p and each integer n >0 there exists a circuit C_n with m inputs and at most p(n) gates, such that C_n generates the intersection of A and {0,1}^n.
a. Show that if a set A has polynomial size circuits, then A has polynomial size generators.
b. Consider the following problem: given a generator G and a word w, decide whether w belongs to the range of G. Prove that this problem is NP-complete. We will cover much of chapter 15.
Problems for Friday, April 9: 15.5.3, 15.5.7, 15.5.16 (you will either have to have some gates with only one output, or many unused outputs at the final level), 15.5.19 (I don't quite understand what is written in part c. Instead, consider in part a the problem where the result is 1 iff X and Y are not equal. Your nondeterministic protocol should, in cases where the inputs are not equal, have at least one computation where the result is 1; in cases where the inputs are equal, there should be no computations with result 1. For part d, I think that the easier direction is to show how to get from a circuit to a communication protocol, so I recommend starting with that.)
Week 13: No classes this week, but we meet again on April 6.
Week 14: We will continue with chapter 15 and show that NC_1 is equal to the class of boolean functions which have polynomial size formulas.
Week 15: We will finish off chapter 15. Then we will cover theorem 19.1 and section 14.3 on oracles.
For Friday, April 23, choose one of the more interesting PSPACE-completeness results from chapter 19 and present it.
Week 16: We will cover chapter 17.
For Friday, May 7: 17.3.11. From JaJa's book, An Introduction to Parallel Algorithms:
a. Show that almost all Boolean functions require circuits of size Omega(2^(n/2)), even when unbounded fan-in is allowed.
b. Given an arithmetic circuit defined by a sequence AC= such that each a_i = 0 or 1, or a_i = a_j + a_k, a_i = a_j - a_k, or a_i = a_j x a_k, for some j,k < i, we are interested in determining whether or not the value of a_n is equal to 1. Show that this problem is P-complete.
Week 17: We will cover theorems 17.12 and 19.8.
No problems, but think about how you would design an interactive proof for an NP-Complete problem or for a Co-NP-Complete problem.
Week 18: We finished with theorem 19.8 and began on chapter 18.
Week 19: We will continue on chapter 18 and introduce quantum computation.
Week 20: We will consider the class MAX-SNP and show that MAX-kSAT does not have a polynomial time approximation scheme, assuming that P is not NP. (We assume that NP=PCP(log n, 1) without proving it.) See chapter 10 of Hochbaum's book on Approximation Algorithms. We will also begin on DNA computation. For this, see the February 1999 Bulletin of the EATCS - Martyn Amos' article.
Last modified: May 17, 1999.
Joan F. Boyar (joan@imada.sdu.dk)

 

   Data protection at SDU ▪ Databeskyttelse på SDU