Affordable Access

Publisher Website

A note on PCP vs. MIP

Authors
Journal
Information Processing Letters
0020-0190
Publisher
Elsevier
Publication Date
Volume
58
Issue
3
Identifiers
DOI: 10.1016/0020-0190(96)00043-9
Keywords
  • Algorithms
  • Complexity
  • Interactive Proof System
Disciplines
  • Communication

Abstract

Abstract Two variants of interactive proof systems have been used to derive intractability of approximation results. The first is the single-round multi-prover model where one verifier can query many provers who cannot communicate among themselves. The second is the oracle model where the verifier queries a non-adaptive oracle. It is known that the oracle model is at least as strong as the one-round multi-prover model but it is not known whether the opposite is true. We partially close this gap.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

[PCP].

on Harefuah September 1983

PCP.

on Southern Medical Journal December 1980

[MIP-1].

on Nihon rinsho. Japanese journal... August 2005

[MIP-1].

on Nihon rinsho. Japanese journal... November 1999
More articles like this..