A PCP characterization of NP with optimal amortized query complexity.

Alex Samorodnitsky Luca Trevisan

Published in: STOC (2000)

Keyphrases

query complexity
worst case
optimal solution
data complexity
np hard
databases
database systems
uniform distribution
membership queries