Probabilistically Checkable Proofs Over the Reals | Zendy

Klaus Meer | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Probabilistically Checkable Proofs Over the Reals

Author(s) -

Klaus Meer

Publication year - 2005

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2004.04.047

Subject(s) - mathematical proof , class (philosophy) , connection (principal bundle) , complexity class , mathematics , discrete mathematics , characterization (materials science) , computer science , combinatorial proof , combinatorics , time complexity , artificial intelligence , physics , geometry , optics

Probabilistically checkable proofs (PCPs) have turned out to be of great importance in complexity theory. On the one hand side they provide a new characterization of the complexity class NP, on the other hand they show a deep connection to approximation results for combinatorial optimization problems. In this paper we study the notion of PCPs in the real number model of Blum, Shub, and Smale. The existence of transparent long proofs for the real number analogue NPR of NP is discussed

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research