IEEE - Institute of Electrical and Electronics Engineers, Inc. - Probabilistic checking of proofs; a new characterization of NP

Author(s): Arora, S. ; Safra, S.
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 January 1992
Conference Location: Pittsburgh, PA, USA
Conference Date: 24 October 1992
Page(s): 2 - 13
ISBN (Paper): 0-8186-2900-2
DOI: 10.1109/SFCS.1992.267824
Regular:

The authors give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in... View More

Advertisement