The complexity class NP consists of search problems where the sought object may be hard to find, but once the object is provided by an all-knowing oracle, it is possible to verify it efficiently and deterministically. However, if we allow ourselves interaction and small probability of error in our verification processes, we can reach higher complexity classes than NP. These “probabilistic proof systems” consist of interactive proofs, zero-knowledge proofs and the main object of the talk, the probabilistically checkable proofs.
In this talk, we will provide a humble introduction to probabilistic proof systems and talk about one of the most important theorems of complexity theory, the PCP theorem. If time allows, we will also show how the PCP theorem implies inapproximability of certain combinatoric optimizatiton problems.