MIP equals NEXP
E364352
MIP equals NEXP is a landmark complexity-theoretic result showing that problems solvable by multi-prover interactive proofs exactly match those solvable in nondeterministic exponential time.
All labels observed (1)
| Label | Occurrences |
|---|---|
| MIP equals NEXP canonical | 1 |
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
complexity-theoretic result
ⓘ
theorem in computational complexity theory ⓘ |
| assertsThat | MIP equals NEXP ⓘ |
| assumesComplexityMeasure | time complexity ⓘ |
| assumesModelOfComputation | Turing machine ⓘ |
| assumesProversAre | computationally unbounded ⓘ |
| assumesVerifierIs | probabilistic polynomial-time machine ⓘ |
| characterizes | power of multiple non-communicating provers ⓘ |
| comparesTo | IP = PSPACE ⓘ |
| describesClass |
languages decidable by multi-prover interactive proofs
ⓘ
languages decidable in nondeterministic exponential time ⓘ |
| equatesComplexityClass |
class of problems solvable by multi-prover interactive proofs
ⓘ
class of problems solvable in nondeterministic exponential time ⓘ |
| formalStatement | MIP = NEXP ⓘ |
| hasAbbreviation | MIP=NEXP ⓘ |
| hasAuthor |
Carsten Lund
ⓘ
Lance Fortnow ⓘ László Babai ⓘ Mario Szegedy ⓘ Shmuel Safra ⓘ |
| hasConsequence |
multi-prover interactive proofs are strictly more powerful than single-prover interactive proofs unless PSPACE = NEXP
ⓘ
nondeterministic exponential time problems admit multi-prover interactive proof systems ⓘ provides basis for later PCP theorem developments ⓘ |
| hasField |
computational complexity theory
ⓘ
theory of interactive proofs ⓘ |
| hasImpactOn |
design of probabilistically checkable proofs
ⓘ
understanding of interactive proof hierarchies ⓘ |
| hasYearOfPublication | 1991 ⓘ |
| impliesContainment |
MIP ⊆ NEXP
ⓘ
NEXP ⊆ MIP ⓘ |
| influences | subsequent work on multi-prover interactive proofs with entangled provers ⓘ |
| isCitedAs | Babai–Fortnow–Lund–Safra–Szegedy theorem ⓘ |
| isContrastedWith | MIP* = RE ⓘ |
| isLandmarkFor |
interactive proof systems
ⓘ
multi-prover interactive proofs ⓘ nondeterministic exponential time ⓘ |
| isProvedUsing |
algebraic encoding of computations
ⓘ
oracularization techniques ⓘ parallel repetition ideas ⓘ |
| isRelatedTo |
PCP theorem
ⓘ
hardness of approximation ⓘ |
| isTaughtIn | graduate complexity theory courses ⓘ |
| originallyAnnouncedIn | late 1980s ⓘ |
| publishedIn | Journal of the ACM ⓘ |
| relatesConcept |
MIP
ⓘ
NEXP ⓘ |
| statesEqualityBetween |
MIP
ⓘ
NEXP ⓘ |
| usesModel | multi-prover interactive proof system ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.