| dbo:abstract
|
- 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. Tots els sistemes de demostració interactius tenen dos requeriments:
* Complets: si l'entrada se certa, el verificador honest (aquell que segueix correctament el protocol) pot ser convençut per un verificador no confiable.
* Solidesa: si l'entrada és falsa, cap provador, inclús si no segueix el protocol, pot convèncer el verificador que és cert, excepte amb una petita probabilitat. S'assumeix que el verificador sempre és honest. La natura específica del sistema, i per tant de la classe de complexitat que defineix depèn de quines restriccions es posen al verificador i de quines habilitats se li donen. Les classes de complexitat més importants amb aquest tipus d'arquitectura són les classes AM i IP. (ca)
- 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)
- 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. Este concepto de cómputo como interacción entre dos partes fue propuesto por y otros y por y otros. Se ha demostrado que el conjunto de todos los lenguajes reconocibles por interacción (llamado clase de complejidad IP) es equivalente al conjunto de todos los lenguajes reconocibles por una máquina de Turing usando espacio polinómico. Usualmente, en un sistema de demostración interactivo, el verificador puede almacenar conocimiento previo. Si ese conocimiento es público (es decir, visible por el demostrador), el sistema de demostración es llamado . Esta noción fue introducida por Badai y otros. Más adelante Goldwasser y Sipser demostraron que el conjunto de lenguajes que tienen pruebas interactivas con conocimiento privado también tienen pruebas interactivas con conocimiento público.
* Datos: Q1665886 (es)
- 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. All interactive proof systems have two requirements:
* Completeness: if the statement is true, the honest prover (that is, one following the protocol properly) can convince the honest verifier that it is indeed true.
* Soundness: if the statement is false, no prover, even if it doesn't follow the protocol, can convince the honest verifier that it is true, except with some small probability. The specific nature of the system, and so the complexity class of languages it can recognize, depends on what sort of bounds are put on the verifier, as well as what abilities it is given—for example, most interactive proof systems depend critically on the verifier's ability to make random choices. It also depends on the nature of the messages exchanged—how many and what they can contain. Interactive proof systems have been found to have some important implications for traditional complexity classes defined using only one machine. The main complexity classes describing interactive proof systems are AM and IP. (en)
- 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)
- 対話型証明系（たいわがたしょうめいけい、英: Interactive proof system）は、2者間のメッセージ交換によって計算をモデル化した計算模型であり、計算複雑性理論で使われる。2者とは、検証者と証明者と呼ばれ、与えられた文字列がある形式言語に属するか否かをメッセージのやり取りによって決定するものである。証明者は無限の計算資源を持つ全能の計算能力を持つが、検証者の方は限定的な計算能力を持つ。メッセージのやり取りは、検証者が証明者による証明に納得して正しいと判断するまで続けられる。 対話型証明系は、必ず次のような2つの要求に従う。
* 完全性: 文が真である場合、プロトコルに正しく従う検証者は、プロトコルに正しく従う証明者の証明に納得する。
* 健全性: 文が偽である場合、証明者がプロトコルに正しく従うかどうかに関わらず、プロトコルに正しく従う検証者は証明者の（真であるという）証明には従わない（小さな確率で納得してしまう可能性はある）。 なお、検証者がプロトコルに従わない場合は問題とはされず、常に検証者を信じるという点に注意されたい。 この系の特徴や関連する複雑性クラスが認識する言語の特徴は、検証者がどのように制限されるかに依存し、また検証者にどのような能力を与えるかに依存する。例えば、多くの対話型証明系は検証者の無作為選択能力に大きく依存する。交換されるメッセージの性質、その頻度や内容も重要である。対話型証明系は、それまで単一の機械で定義されてきた複雑性クラスに多大な影響を与えた。対話型証明系を使って定義された主な複雑性クラス（実際には複雑性クラスの階層）としては、AM、MA、、PCP などがある。 (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. Todas as provas de sistema interativo tem dois requisitos:
* Completude: se a afirmação é verdadeira, o verificador (isto é, que segue o protocolo adequadamente) irá ser convencido deste fato por um provador honesto.
* Corretude: se uma afirmação é falsa, nenhum provador, mesmo se ele não segue o protocolo, conseguirá convencer o verificador honesto de que isso é verdade, exceto com pequena probabilidade. Assume-se que o verificador é sempre honesto. A natureza específica do sistema, e assim a classe de complexidade das linguagens que podem ser reconhecidas, depende de que tipo de limites são colocados no verificador, bem como quais habilidades são dadas — por exemplo, muitos sistemas de provas interativas dependem criticamente da habilidade do verificador de fazer escolhas aleatórias. Isso também depende da natureza da mensagem trocada — quantas e quais eles podem conter. Sistemas interativos de prova foram encontrados para ter algumas implicações importantes para complexidade de classes tradicional definida usando somente máquinas. As principais classes de complexidade que descrevem sistemas de provas interativos são AM e IP. (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)
|
| 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?width=300)
.svg){kind=link}
.svg){kind=link}