Mikołaj Bojańczyk

## Computational Complexity / Złożoność obliczeniowa 2020/2021

A course on computational complexity for 4th year students (1st year of MSc programme).

## Rules

• 10% quizes. Every lecture will have a quiz on moodle with several yes/no questions to check if you are paying attention.
• 40% homeworks. There will be 5 homeworks, some programming and some theory.
• 50% oral exam. At the end, there will be an oral exam.

Notice that there is no written exam, midterm or final. That is why the homeworks are bigger than usual. The exact point thresholds for the grades will appear later, but I promise that 50% (or less) will give you a passing grade (dostateczny).

The oral exams will be in the exercise groups. You can negotiate the date of the oral exam with your exercise teacher (ćwiczeniowiec), in justified cases it is possible to have the oral exam at an earlier date.

How much effort is expected?

I expect that you, as a smart student, will:

1. Watch the lecture each week, using 60-90 minutes, including pauses
2. Take 10-20 minutes to solve the quiz
3. Participate in the exercise session
4. Take, on average, 5 hours to solve each of the 5 homework assignments
5. Take around 15-20 hours to prepare for the oral exam (e.g. you rewatch every lecture and think about it a bit)
The difficulties of the quizes, homeworks, and the oral exams will be designed with these criteria in mind. I will send surveys to check if these criteria are met.
Quizes. I expect that you do the quiz on your own, without discussing the answers with colleagues. For this reason, you do not need to obsess over perfect answers – at the end of the semester you will still get a full score for the quiz if you had 80% answers right. The purpose of the quiz is to see if you understand the lecture well.
Homework. There will be around 5 homeworks, some programming, some not. It is ok if you discuss the homework with your colleagues, but you should write your own answer alone.
Oral exam. For each of the lectures, I will publish corresponding questions. The questions at the oral exam will be selected from these. Some questions will be marked as “5” questions, which will be needed only if you want to get the top grade “5”.

## Lectures

The lectures include sound (press the play button on the slide, or the space key on the keyboard), so there will be no videos. This is a slide system that I am developing, so please send me bug reports!

These lectures are roughly once per week, but some lectures are longer so there is no exact correspondence.

Lecture 1. Turing machines (October 20)

• Definition of Turing machines
• Decidability and semi-decidability
• Undecidability of the halting problem

Questions for the oral exam:

• prove that the halting problem is undecidable

Lecture 2. Space and time (October 27)

• The basic complexity classes: NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME,
• separation of P and EXPTIME
• PSPACE = NPSPACE (Savitch)
• machines in finite space that always halt (Sipser Theorem)
• NL = coNL (Immerman and Szelepcsenyi Theorem)

Questions for the oral exam:

• Prove that P < EXPTIME
• Prove that PSPACE = NPSPACE
• Prove the Sipser Theorem
• Prove the Immerman and Szelepcsenyi Theorem

Lecture 3. Reductions and complete problems (November 3 and 10)

• Turing and Karp reductions
• Sat as an NP-complete problem
• QBF as a PSPACE-complete problem
• alternating reachability as P-complete problem
• the Baker-Gill-Solovay Theorem.

Questions for the oral exam:

• Explain the difference between Turing and Karp reductions
• Prove that Sat is NP-complete, and that QBF is PSPACE-complete
• Prove the Baker-Gill-Solovay Theorem

Lecture 4. Introduction to circuits (November 10)

• Circuits and their “parallel algorithm” intuition
• Circuit descriptions of P and P/p0ly
• AC and NC

Questions for the oral exam:

• Define the class P/Poly and show that it is equal to polynomial size circuits

Lecture 5. Parity not in AC0 (November 17)

• parity is not in AC

Questions for the oral exam:

• (Only if you want grade 5) Prove that parity is not in AC

Lecture 6. Randomisation (November 24 and December 1)

• the class RP ⊆ BPP ⊆ PP
• examples of RP algorithms, including polynomial identity testing and perfect matchings
• PP contains NP

Questions for the oral exam:

• Define the classes RP, BPP and PP
• Give RP algorithms for: evaluating straight line programs and polynomial identity testing

Lecture 7. Derandomisation (December 1 and 8)

• two techniques for derandomisation illustrated on max cut
• Adleman’s Theorem on BPP ⊆ P/Poly

Questions for the oral exam:

• Explain the two derandomised algorithms for max cut
• Prove Adleman’s Theorem

Lecture 8. Fine-grained complexity (December 8 and 15)

• SETH ⟹ Orthogonal vectors conjecture
• Orthogonal vectors conjecture  ⟹ NFA evaluation needs quadratic algorithms

Questions for the oral exam:

• Prove: SETH ⟹ Orthogonal vectors conjecture
• Prove: Orthogonal vectors conjecture  ⟹ NFA evaluation needs quadratic algorithms

Lecture 9. Parametrized complexity (December 22)

• An algorithm for vertex cover that is linear when the size of the vertex cover is fixed
• The class FPT and FPT-reductions
• An FPT algorithm for 3-colourability on bounded treewidth

Questions for the oral exam:

• Define the class FPT and show that vertex cover is in it
• Show FPT reductions, both ways, between the k-clique problem and Turing machines with accepting computations of length k.
• Prove that 3-colourability is FPT, where the parameter is treewidth

The remaining lectures are not part of the oral exam.

Lecture 10. Quantum computation (January 12)

• BPP via probabilistic circuits
• quantum circuits
• the class BQP (bounded error quantum polynomial time)

Lecture 11. Simon’s algorithm (January 17)

• Simon’s algorithm

## Homework

There will be several homework assignments, including programming assignments.