| rdfs:comment
| - En théorie de la complexité, un protocole Arthur-Merlin est un système de preuve interactive dans lequel on impose que les lancers de pièces du vérificateur soient publics (c'est-à-dire également connus du démonstrateur). Cette notion a été introduite par László Babai en 1985. Godwasser et Sipser ont prouvé en 1986 que tous les langages avec preuves interactives de longueur arbitraire avec aléatoire privé peuvent aussi être décidés par des preuves interactives avec aléatoire public. (fr)
- 計算複雑性理論におけるArthur–Merlinプロトコル(Arthur–Merlin protocol)あるいは、Merlin–Arthurプロトコル(Merlin–Arthur protocol)は、検証者のコイン投げが公開されている(使用する乱数が証明者に知られている)タイプの対話型証明プロトコルである。そのようなプロトコルを持つ言語のクラスとして、AM及びMAがそれぞれ定義され、本項では主にこのクラスについて説明する。によって導入された。 (ja)
- En teoria de la complexitat, la classe de complexitat AM (també coneguda per AM[2]) és el conjunt dels problemes de decisió que poden ser resolts en temps polinòmic per un de dos missatges. Només hi ha un parell pregunta/resposta: Arthur llança unes monedes i envia tots els resultats a Merlin, Merlin respon i Arthur decideix si accepta o no. Es requereix que
* Si la resposta és SI, llavors Merlin pot actuar de manera que Arthur accepti amb probabilitat d'almenys 2/3
* Si la resposta és NO, llavors faci el que faci Merlin, Arthur rebutja amb probabilitat d'almenys 2/3. (ca)
- In computational complexity theory, an Arthur–Merlin protocol, introduced by , is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). proved that all (formal) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins. (en)
- En la teoría de complejidad computacional, un protocolo Arthur–Merlin es un sistema de prueba interactivo en el que los lanzamientos de monedas del verificador están obligados a ser públicos (es decir, también conocidos por el probador). Esta noción fue introducida por . demostraron que todos los lenguajes formales con pruebas interactivas de longitud arbitraria con monedas privadas también tienen pruebas interactivas con monedas públicas. (es)
- Na área da Complexidade computacional, um protocolo Arthur–Merlin é um sistema de prova interativa no qual os lançamentos de moeda do verificador são obrigados a serem públicos. Essa noção foi introduzida por . provaram que todas as linguagens com provas interativas de comprimento arbitrário com moedas privadas também têm provas interativas com moedas públicas. (pt)
|
| has abstract
| - En teoria de la complexitat, la classe de complexitat AM (també coneguda per AM[2]) és el conjunt dels problemes de decisió que poden ser resolts en temps polinòmic per un de dos missatges. Només hi ha un parell pregunta/resposta: Arthur llança unes monedes i envia tots els resultats a Merlin, Merlin respon i Arthur decideix si accepta o no. Es requereix que
* Si la resposta és SI, llavors Merlin pot actuar de manera que Arthur accepti amb probabilitat d'almenys 2/3
* Si la resposta és NO, llavors faci el que faci Merlin, Arthur rebutja amb probabilitat d'almenys 2/3. Es pot reformular la definició de la següent manera: un llenguatge L és a AM si existeix una màquina de Turing determinista en temps polinòmic i els polinomis p i q tals que:
* si x és a L, llavors
* si x no és a L, llavors La segona condició es pot escriure d'aquesta forma alternativa:
* si x no és a L, llavors z és la prova que envia Merlin (de mida polinòmica) i y és la cadena aleatòria que envia Arthur, que també està fitada polinòmicament. El problema de saber si dos grafs no son isomorfs pertany a aquesta classe. (ca)
- In computational complexity theory, an Arthur–Merlin protocol, introduced by , is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). proved that all (formal) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins. Given two participants in the protocol called Arthur and Merlin respectively, the basic assumption is that Arthur is a standard computer (or verifier) equipped with a random number generating device, while Merlin is effectively an oracle with infinite computational power (also known as a prover). However, Merlin is not necessarily honest, so Arthur must analyze the information provided by Merlin in response to Arthur's queries and decide the problem itself. A problem is considered to be solvable by this protocol if whenever the answer is "yes", Merlin has some series of responses which will cause Arthur to accept at least 2⁄3 of the time, and if whenever the answer is "no", Arthur will never accept more than 1⁄3 of the time. Thus, Arthur acts as a probabilistic polynomial-time verifier, assuming it is allotted polynomial time to make its decisions and queries. (en)
- En la teoría de complejidad computacional, un protocolo Arthur–Merlin es un sistema de prueba interactivo en el que los lanzamientos de monedas del verificador están obligados a ser públicos (es decir, también conocidos por el probador). Esta noción fue introducida por . demostraron que todos los lenguajes formales con pruebas interactivas de longitud arbitraria con monedas privadas también tienen pruebas interactivas con monedas públicas. Dados dos participantes en el protocolo llamado Arthur y Merlin respectivamente, la suposición básica es que Arthur es una computadora estándar (o verificador) equipada con un dispositivo generador de números aleatorios, mientras que Merlin es efectivamente un oráculo con un poder computacional infinito (también conocido como prover); pero Merlin no es necesariamente honesto, por lo que Arthur debe analizar la información proporcionada por Merlin en respuesta a las preguntas de Arthur y decidir el problema en sí. Un problema se considera que es solucionable mediante este protocolo si cada vez que la respuesta es "sí", Merlin tiene alguna serie de respuestas que hará que Arthur para aceptar al menos 2/3 de las veces y si cada vez que la respuesta es "no", Arthur nunca aceptará más de 1/3 del tiempo. Por lo tanto, Arthur actúa como un verificador probabilístico de tiempo polinómico, suponiendo que se le asigna tiempo polinómico para tomar sus decisiones y consultas. (es)
- En théorie de la complexité, un protocole Arthur-Merlin est un système de preuve interactive dans lequel on impose que les lancers de pièces du vérificateur soient publics (c'est-à-dire également connus du démonstrateur). Cette notion a été introduite par László Babai en 1985. Godwasser et Sipser ont prouvé en 1986 que tous les langages avec preuves interactives de longueur arbitraire avec aléatoire privé peuvent aussi être décidés par des preuves interactives avec aléatoire public. (fr)
- 計算複雑性理論におけるArthur–Merlinプロトコル(Arthur–Merlin protocol)あるいは、Merlin–Arthurプロトコル(Merlin–Arthur protocol)は、検証者のコイン投げが公開されている(使用する乱数が証明者に知られている)タイプの対話型証明プロトコルである。そのようなプロトコルを持つ言語のクラスとして、AM及びMAがそれぞれ定義され、本項では主にこのクラスについて説明する。によって導入された。 (ja)
- Na área da Complexidade computacional, um protocolo Arthur–Merlin é um sistema de prova interativa no qual os lançamentos de moeda do verificador são obrigados a serem públicos. Essa noção foi introduzida por . provaram que todas as linguagens com provas interativas de comprimento arbitrário com moedas privadas também têm provas interativas com moedas públicas. O pressuposto básico é que Arthur é um computador padrão (ou verificador) equipado com um dispositivo gerador de números aleatórios, enquanto Merlin é efetivamente um oráculo com poder computacional infinito (também conhecido como um provador); mas Merlin não é necessariamente honesto, então Arthur deve analisar as informações fornecidas por Merlin em resposta às consultas de Arthur e decidir o problema por si só. Um problema é considerado solúvel por este protocolo se sempre que a resposta for "sim", Merlin possui algumas series de respostas tal que Arthur vai aceitar em pelo menos 2/3 das vezes, e sempre que a resposta for "não" , Arthur nunca vai aceitar em mais de 1/3 das vezes. Portanto, Arthur age como um verificador probabilístico de tempo polinomial, supondo que a ele é alocado tempo polinomial para tomar suas decisões e consultas. (pt)
|
![[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)
