# What's the polynomial involved in the PCP theorem?

Statements of the PCP theorem always speak of a proof of length $poly(n)$. But what polynomial is that exactly? Could you actually construct the PCP for some mathematical fact in real life?

• Each problem has it's own polynomial, and there exist problems with arbitrary large polynomials, otherwise it wouldn't be denoted so. – rus9384 Jul 14 '17 at 23:24
• For 3SAT the polynomial is $n^{1+o(1)}$, see for example Moshkovitz–Raz and the references therein. – Yuval Filmus Jul 15 '17 at 6:09
• This is more related to the definition of NP than to PCP. One of the defined requirements for a problem to be in NP is that for each yes-answer there exists a certificate of polynomial size, that is at most $O(n^c)$ for some constant c you might choose. – Albert Hendriks Jan 4 '18 at 8:40