Statements (22)
Predicate | Object |
---|---|
gptkbp:instanceOf |
theoretical computer science
|
gptkbp:characterizedBy |
problems solvable by an interactive proof system in polynomial time
|
gptkbp:contains |
gptkb:co-NP
NP |
gptkbp:definedIn |
theoretical computer science
|
gptkbp:equivalentTo |
gptkb:PSPACE
|
gptkbp:fullName |
gptkb:Interactive_Polynomial_time
|
gptkbp:hasApplication |
cryptography
zero-knowledge proofs |
gptkbp:hasMajorResult |
IP = PSPACE
|
gptkbp:hasProperty |
randomized algorithms
interactive communication prover is computationally unbounded verifier runs in polynomial time |
https://www.w3.org/2000/01/rdf-schema#label |
IP complexity class
|
gptkbp:introduced |
gptkb:Adi_Shamir
|
gptkbp:introducedIn |
1990
|
gptkbp:relatedTo |
gptkb:Arthur-Merlin_protocol
interactive proof system PSPACE complexity class |
gptkbp:bfsParent |
gptkb:public-coin_interactive_proof
|
gptkbp:bfsLayer |
6
|