IP (complexity)
id:
ip-complexity-165-14661674
title:
IP (complexity)
text:
In computational complexity theory, the class IP (interactive proof) is the class of problems solvable by an interactive proof system. It is equal to the class PSPACE. The result was established in a series of papers: the first by Lund, Karloff, Fortnow, and Nisan showed that co-NP had multiple prover interactive proofs; and the second, by Shamir, employed their technique to establish that IP=PSPACE. The result is a famous example where the proof does not relativize. The concept of an interactiv
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/IP_(complexity)
date created:
2005-07-09T00:35:56Z
date modified:
2024-08-29T14:00:03Z
main entity:
{"identifier":"Q5973158","url":"https://www.wikidata.org/entity/Q5973158"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/b/b0/Interactive_proof_%28complexity%29.svg","width":248,"height":164}
fields total:
13
integrity:
15