*Probabilistically checkable proofs (PCPs)* can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and incorrect claims are rejected with high probability (regardless of the given alleged proof). We consider two possible features of PCPs:

A PCP is

*strong*if it rejects an alleged proof of a correct claim with probability proportional to its distance from some correct proof for that claim.A PCP is

*smooth*if each location in a proof is queried with equal probability.

We prove that all sets in **NP** have a smooth and strong PCP of polynomial length that can be verified based on a constant number of queries. We do so by following the proof of the PCP theorem of Arora, Lund, Motwani, Sudan and Szegedy (*JACM*, 1998), providing a stronger analysis of the Hadamard and Reed–Muller based PCPs and a refined PCP composition theorem. In fact, we show that any set in **NP** has a smooth strong *canonical* PCP of Proximity (PCPP), meaning that there is an efficiently computable bijection of **NP** witnesses to correct proofs.

This improves on the recent result of Dinur, Gur and Goldreich (*ITCS*, 2019) that constructs strong canonical PCPPs that are inherently non-smooth. Our result implies the hardness of approximating the satisfiability of *“stable”* 3CNF formulae with *bounded variable occurrence*, proving a hypothesis used in the work of Friggstad, Khodamoradi and Salavatipour (*SODA*, 2019). Here *stability* means that the number of clauses violated by an assignment is proportional to its distance from a satisfying assignment (in the relative Hamming metric).

Type

Publication

computational complexity (2021); The 11th Innovations in Theoretical Computer Science conference (ITCS 2020)