Probabilistically Checkable Proofs or more succinctly PCPs have played a significant role in complexity theory in the last decade. A PCP is a written proof that is verified by a probabilistic verifier that reads a very small portion of the proof.
Not only are PCPs interesting in their own right but they also lead to strong inapproximability results for interesting optimization problems.
As a concrete example take satisfiability of Boolean formulas. A classical NP-proof that a formula is satisfiable is given by an assignment that satisfies the formula and this is verified by reading the entire proof and checking that indeed the assignment satisfies the formula.
The PCP-theorem says that for satisfiability and hence for any NP-statement, there is a PCP that allows proofs of polynomial size and such that the verifier reads a constant number of bits, always accepts a correct proof and rejects and proof of a false NP-statement with probability at least 1/2.
In the application to inapproximability it is important to optimize some of the parameters of the PCP and in particular we will be interested in proofs where the verifier only reads three bits.
In the lecture we will explain, but not prove the PCP-theorem and discuss the connection to inapproximability.
If all present understand Swedish the lecture will be given in Swedish and otherwise in English.