Das PCP-Theorem ist ein Satz aus der theoretischen Informatik (Komplexitätstheorie). Es beruht auf dem Konzept des zufällig verifizierbaren Beweises eines mathematischen Satzes (probabilistic checkable proof, PCP), der wiederum auf das Konzept Interaktiver Beweissysteme zurückgeht, die Anfang der 1980er Jahre von Shafi Goldwasser, Charles Racko...