Lecture 1 - Introduction
Introduction of the course, and of the topic of computationa complexity. We discussed generically what it means to prove a lower bound, i.e., to show that it is impossible to compute some function within a certain amount of resources.
An impossibility result is a mathematical statement about a computational model. We can focus on powerful computational model and only prove weak and conditional lower bounds, and we can consider concrete and restricted models where we can prove tight one.
We saw the example of two loer bounds:
- Parity on \(n\) variables requires CNF formulas of size \(\Theta(n 2^n)\)
- (Sketch) Equality of two strings of \(n\) bits requires \(n\) bits of communication.
Homework:
- read Introduction and Chapter 0 of textbook [AB]