(poly( n),poly( n))-restricted verifiers are unlikely to exist for languages in NP

DOI10.1007/3-540-61550-4_162MaRDI QIDQ4375813zbMATH OpenFDO

Authors Dimitris Fotakis, P. G. Spirakis

Publication date 11 June 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61550-4_162

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1256636
• Probabilistic checking of proofs
• Probabilistic verification of proofs
• Proof verification and the hardness of approximation problems

Cited in

(2)

• The inapproximability of non-NP-hard optimization problems.
• Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries

This page was built for publication: \((\text{poly}(\log\log n),\text{poly}(\log\log n))\)-restricted verifiers are unlikely to exist for languages in \({\mathcal NP}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4375813)