Complexity theory, proofs and approximation
2005 (English)In: European Congress of Mathematics / [ed] Laptev, A, 2005, 733-750 p.Conference paper (Refereed)
We give a short introduction to some questions in complexity theory and proceed to describe some recent developments. In particular, we discuss probabilistically checkable proofs and their applications in establishing inapproximability results. In a traditional proof the proof-checker reads the entire proof and decides deterministically whether the proof is correct. In a probabilistically checkable proof the proof-checker randomly verifies only a very small portion of the proof but still cannot be fooled into accepting a false claim except with small probability.
Place, publisher, year, edition, pages
2005. 733-750 p.
IdentifiersURN: urn:nbn:se:kth:diva-43290DOI: 10.4171/009-1/46ISI: 000231730600046ISBN: 3-03719-009-4OAI: oai:DiVA.org:kth-43290DiVA: diva2:448604
4th European Congress of Mathematics (4ECM) Location: Stockholm, SWEDEN Date: JUN 27-JUL 02, 2004
QC 201110172011-10-172011-10-142012-09-25Bibliographically approved