Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/IP_(complexity)> ?p ?o }
Showing triples 1 to 78 of
78
with 100 triples per page.
- IP_(complexity) abstract "In computational complexity theory, the class IP (which stands for Interactive Polynomial time) is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985. An interactive proof system consists of two machines, a prover, P, which presents a proof that a given string n is a member of some language, and a verifier, V, that checks that the presented proof is correct. The prover is assumed to be infinite in computation and storage, while the verifier is a probabilistic polynomial-time machine with access to a random bit string whose length is polynomial on the size of n. These two machines exchange a polynomial number, p(n), of messages and once the interaction is completed, the verifier must decide whether or not n is in the language, with only a 1/3 chance of error. (So any language in BPP is in IP, since then the verifier could simply ignore the prover and make the decision on its own.)".
- IP_(complexity) thumbnail Interactive_proof_(complexity).svg?width=300.
- IP_(complexity) wikiPageExternalLink 0907.4737.
- IP_(complexity) wikiPageExternalLink compip.
- IP_(complexity) wikiPageExternalLink frip.
- IP_(complexity) wikiPageExternalLink ipp.
- IP_(complexity) wikiPageExternalLink mip.
- IP_(complexity) wikiPageExternalLink qip.
- IP_(complexity) wikiPageExternalLink qip2.
- IP_(complexity) wikiPageExternalLink 146585.146613.
- IP_(complexity) wikiPageExternalLink citation.cfm?doid=146585.146609.
- IP_(complexity) wikiPageExternalLink citation.cfm?id=63434.
- IP_(complexity) wikiPageExternalLink 1985-stoc.pdf.
- IP_(complexity) wikiPageExternalLink 1986-stoc.pdf.
- IP_(complexity) wikiPageID "2197070".
- IP_(complexity) wikiPageLength "29661".
- IP_(complexity) wikiPageOutDegree "37".
- IP_(complexity) wikiPageRevisionID "673782286".
- IP_(complexity) wikiPageWikiLink Adi_Shamir.
- IP_(complexity) wikiPageWikiLink Arthur–Merlin_protocol.
- IP_(complexity) wikiPageWikiLink BPP_(complexity).
- IP_(complexity) wikiPageWikiLink BQP.
- IP_(complexity) wikiPageWikiLink Bounded-error_probabilistic_polynomial.
- IP_(complexity) wikiPageWikiLink Carsten_Lund.
- IP_(complexity) wikiPageWikiLink Category:Articles_containing_proofs.
- IP_(complexity) wikiPageWikiLink Category:Probabilistic_complexity_classes.
- IP_(complexity) wikiPageWikiLink Charles_Rackoff.
- IP_(complexity) wikiPageWikiLink Computational_complexity_theory.
- IP_(complexity) wikiPageWikiLink EXPTIME.
- IP_(complexity) wikiPageWikiLink Error-correcting_code.
- IP_(complexity) wikiPageWikiLink Formal_language.
- IP_(complexity) wikiPageWikiLink Forward_error_correction.
- IP_(complexity) wikiPageWikiLink Graph_isomorphism_problem.
- IP_(complexity) wikiPageWikiLink Interactive_proof_system.
- IP_(complexity) wikiPageWikiLink Lance_Fortnow.
- IP_(complexity) wikiPageWikiLink Laszlo_Babai.
- IP_(complexity) wikiPageWikiLink László_Babai.
- IP_(complexity) wikiPageWikiLink NP-complete.
- IP_(complexity) wikiPageWikiLink NP-completeness.
- IP_(complexity) wikiPageWikiLink NP_(complexity).
- IP_(complexity) wikiPageWikiLink Noam_Nisan.
- IP_(complexity) wikiPageWikiLink Non-deterministic_Turing_machine.
- IP_(complexity) wikiPageWikiLink Nondeterministic_Turing_machine.
- IP_(complexity) wikiPageWikiLink Oracle_machine.
- IP_(complexity) wikiPageWikiLink PP_(complexity).
- IP_(complexity) wikiPageWikiLink PSPACE.
- IP_(complexity) wikiPageWikiLink QIP_(complexity).
- IP_(complexity) wikiPageWikiLink Quantum_Interactive_Protocol.
- IP_(complexity) wikiPageWikiLink Quantum_computer.
- IP_(complexity) wikiPageWikiLink Quantum_computing.
- IP_(complexity) wikiPageWikiLink Shafi_Goldwasser.
- IP_(complexity) wikiPageWikiLink Sharp-SAT.
- IP_(complexity) wikiPageWikiLink Silvio_Micali.
- IP_(complexity) wikiPageWikiLink Truth_value.
- IP_(complexity) wikiPageWikiLink File:Interactive_proof_(complexity).svg.
- IP_(complexity) wikiPageWikiLinkText "IP (complexity)".
- IP_(complexity) wikiPageWikiLinkText "IP = PSPACE".
- IP_(complexity) wikiPageWikiLinkText "IP".
- IP_(complexity) wikiPageWikiLinkText "interactive proof system".
- IP_(complexity) hasPhotoCollection IP_(complexity).
- IP_(complexity) wikiPageUsesTemplate Template:CZoo.
- IP_(complexity) wikiPageUsesTemplate Template:ComplexityClasses.
- IP_(complexity) wikiPageUsesTemplate Template:Main.
- IP_(complexity) subject Category:Articles_containing_proofs.
- IP_(complexity) subject Category:Probabilistic_complexity_classes.
- IP_(complexity) hypernym Problems.
- IP_(complexity) type Disease.
- IP_(complexity) comment "In computational complexity theory, the class IP (which stands for Interactive Polynomial time) is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985.".
- IP_(complexity) label "IP (complexity)".
- IP_(complexity) sameAs IP_(complexité).
- IP_(complexity) sameAs IP_(복잡도).
- IP_(complexity) sameAs m.06v64d.
- IP_(complexity) sameAs Q5973158.
- IP_(complexity) sameAs Q5973158.
- IP_(complexity) sameAs IP_(複雜度).
- IP_(complexity) wasDerivedFrom IP_(complexity)?oldid=673782286.
- IP_(complexity) depiction Interactive_proof_(complexity).svg.
- IP_(complexity) isPrimaryTopicOf IP_(complexity).