scientific article; zbMATH DE number 1114044

MaRDI QIDQ4375813zbMATH OpenFDO

Authors Dimitris Fotakis, P. G. Spirakis

Publication date 11 June 1998

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:

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