Is P = NP? This is the most famous open problem in computer science. A popular approach to attack this problem is to look for a proof of a nonpolynomial lower bound for the circuit complexity of the characteristic function of a language in NP. But no nonlinear lower bound for such a function is known. Can we multiply two integers in linear time or can we prove an Ω(n log n) lower bound for the circuit complexity of the multiplication of two n-bit numbers? Understanding the power of negations is one of the most challenging problems of computer science. The main topic of this lecture is the development of techniques for proving lower bounds for the complexity of Boolean functions.

The second oral examination will be held on Tuesday, the 27th of August 2019. The examinations will be performed in room 2.058. This is some If you have not yet your exact examination time , please write an e-mail to Adrian Schmitz as soon as possible.

• 1st lecture notes
• 2nd lecture notes
• 3rd lecture notes
• 4th lecture notes
• 5th lecture notes

Tutorial presence and exercise sheets are voluntary, but recommended. You can choose freely the tutorial group to participate and you do not have to hand in the solution of the exercise sheets. Also, there are no other requirements to take part in the oral examination as to register in BASIS.

• 1st exercise
• 2nd exercise
• 3rd exercise
• 4th exercise
• 5th exercise
• 6th exercise
• 7th exercise
• 8th exercise