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?

  • 2
    $\begingroup$ Each problem has it's own polynomial, and there exist problems with arbitrary large polynomials, otherwise it wouldn't be denoted so. $\endgroup$ – rus9384 Jul 14 '17 at 23:24
  • $\begingroup$ For 3SAT the polynomial is $n^{1+o(1)}$, see for example Moshkovitz–Raz and the references therein. $\endgroup$ – Yuval Filmus Jul 15 '17 at 6:09
  • $\begingroup$ 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. $\endgroup$ – Albert Hendriks Jan 4 '18 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.