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.

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.

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.)

Problems for Friday, March 5:

Whatever we don't finish from last week, plus 7.4.7 and 8.4.2.

On Friday, March 12, we will finish off problem 7.4.17 and do 7.4.7 and 8.4.2.

Problems for Friday, March 19: 10.4.6, the subsection of 11.1 on symbolic determinants, 11.5.14.

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

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.)

For Friday, April 23, choose one of the more interesting PSPACE-completeness results from chapter 19 and present it.

For Friday, May 7: 17.3.11. From JaJa's book,

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=

No problems, but think about how you would design an interactive proof for an NP-Complete problem or for a Co-NP-Complete problem.

Last modified: May 17, 1999. Joan F. Boyar (joan@imada.sdu.dk)