scientific article; zbMATH DE number 1114044

zbMATH Open0889.68059MaRDI QIDQ4375813FDOQ4375813

P. G. Spirakis, Dimitris Fotakis

Publication date: 11 June 1998

Title of this publication is not available (Why is that?)

Recommendations

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

Mathematics Subject Classification ID

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

Cited In (2)

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

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)