PCP theorem
type: Item
Freebase ID: /m/08jszr
instance of: theorem
award received: Gödel Prize
defining formula: N P = P C P [ O ( log n ) , O ( 1 ) ]
named after: probabilistically checkable proof
Microsoft Academic ID: 88606757
part of: list of theorems
Wikidata QID: Q1140200
label: PCP-Theorem @de
description: theorem in complexity theory that every problem in NP has probabilistically checkable proofs
description: mathematischer Satz @de