| rdfs:comment
| - Ein interaktives Beweissystem ist ein Begriff aus der Komplexitätstheorie. Dabei wird eine abstrakte Maschine, in welcher die Informationsverarbeitung durch den Austausch von Nachrichten realisiert ist, beschrieben. Ein interaktives Beweissystem muss die Completeness und Soundnessbedingung erfüllen. Sie wurden 1985 von Shafi Goldwasser, Charles Rackoff und Silvio Micali eingeführt (wobei Preprints bis auf 1982 zurückgingen) und unabhängig von László Babai 1985, der darüber später ausführlich mit Shlomo Moran veröffentlichte. Die Autoren erhielten dafür den ersten Gödel-Preis 1993. (de)
- En théorie de la complexité des algorithmes, un système de preuve interactive est un protocole formel de démonstration de théorèmes qui fait intervenir deux participants qui échangent des messages. Cela permet de définir des classes de complexité intéressantes, notamment la classe IP qui est le modèle utilisé dans le théorème PCP qui caractérise la classe NP. (fr)
- En teoria de la complexitat, un sistema de demostració interactiu és una màquina abstracta que modela la computació com un intercanvi de missatges entre dues parts. Aquestes parts, el Verificador i el Provador, es comuniquen intercanviant-se missatges per determinar si una cadena donada pertany a un llenguatge o no. El provador te tota la potència de càlcul que calgui però no se'n pot confiar, i el verificador té una potència de càlcul fitada. S'intercanvien missatges entre l'un i l'altre fins que el verificador creu que la resposta és correcta. S'assumeix que el verificador sempre és honest. (ca)
- In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct. (en)
- Un sistema de demostración interactivo (IP) es un concepto en teoría de la complejidad computacional que modela cómputos como el intercambio de mensajes entre dos partes. Las partes son el verificador y el demostrador, quienes interactúan por intercambio de mensajes para demostrar la pertenencia o no de una palabra dada a un lenguaje. El demostrador dispone de todos los recursos que necesite pero el verificador tiene un poder de cómputo acotado. El verificador realiza preguntas al demostrador un número limitado de veces para determinar si la palabra dada pertenece o no al lenguaje. (es)
- 対話型証明系（たいわがたしょうめいけい、英: Interactive proof system）は、2者間のメッセージ交換によって計算をモデル化した計算模型であり、計算複雑性理論で使われる。2者とは、検証者と証明者と呼ばれ、与えられた文字列がある形式言語に属するか否かをメッセージのやり取りによって決定するものである。証明者は無限の計算資源を持つ全能の計算能力を持つが、検証者の方は限定的な計算能力を持つ。メッセージのやり取りは、検証者が証明者による証明に納得して正しいと判断するまで続けられる。 対話型証明系は、必ず次のような2つの要求に従う。
* 完全性: 文が真である場合、プロトコルに正しく従う検証者は、プロトコルに正しく従う証明者の証明に納得する。
* 健全性: 文が偽である場合、証明者がプロトコルに正しく従うかどうかに関わらず、プロトコルに正しく従う検証者は証明者の（真であるという）証明には従わない（小さな確率で納得してしまう可能性はある）。 なお、検証者がプロトコルに従わない場合は問題とはされず、常に検証者を信じるという点に注意されたい。 (ja)
- Na teoria da complexidade, um sistema de prova interativa é uma máquina abstrata que formula computação como a troca de mensagens entre duas partes. As duas partes, o verificador e o provador, interagem através da troca de mensagens, a fim de verificar se uma determinada cadeia pertence a uma linguagem ou não. O provador é muito poderoso e possui recursos computacionais ilimitados, mas não é confiável, enquanto que o verificador tem poder computacional limitado. Mensagens são enviadas entre o verificador e o provador até que o verificador tenha uma resposta ao problema e tenha "convencido" ele mesmo de que está correto. (pt)
- 在计算复杂性理论中，交互式证明体系（下简称交互证明）是一类计算模型。像其它计算模型一样，我们的目标是对一个语言L，和一个给定的输入x，判断x是否在L中。交互式证明体系由两个实体：验证者（verifier）和证明者（prover）组成，两者都可以看作是某类图灵机。而它的计算过程为：给定了输入x，通过验证者和证明者之间交换信息，最终，由验证者来根据证明者给出的信息，判断给定的输入是不是在语言L中。 交互证明的基本假设是：证明者在计算能力上是无限的，在概率多项式时间（BPP (複雜度)）的图灵机。一般来说，对给定的L，我们关注的是交互证明中验证者V这一角色，并对它加以如下的要求：
* 完备性（completeness）：如果x∈L，那么存在诚实的证明者P，使得V与P的交互之后，输出“x∈L”；
* 可靠性（soundness）：如果x∉L，那么对任意的证明者P，V与P交互之后，输出“x∈L”的概率很小（可以认为小于某一常数）。 如果对L，这样的验证者存在，那么我们说L有这样的一个交互体系。 (zh)
|
.svg)
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)