This HTML5 document contains 106 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n27http://www.cs.princeton.edu/theory/complexity/
n22http://theory.lcs.mit.edu/~madhu/ST05/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n10http://dbpedia.org/resource/File:
dbpedia-cahttp://ca.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
n21https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
n18http://dbpedia.org/resource/NP/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
n23http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
n9http://dbpedia.org/resource/P/
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbr:List_of_complexity_classes
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:List_of_computability_and_complexity_topics
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:NP_(complexity)
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:QMA
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:Arthur-Merlin_protocol
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
dbo:wikiPageRedirects
dbr:Arthur–Merlin_protocol
Subject Item
n9:poly
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:Time_complexity
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:Distinguishing_coloring
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:PP_(complexity)
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:AM
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:AI-complete
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:AM_(complexity)
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
dbo:wikiPageRedirects
dbr:Arthur–Merlin_protocol
Subject Item
dbr:Karp–Lipton_theorem
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:Stathis_Zachos
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:Arthur–Merlin_protocol
rdf:type
yago:Collection107951464 yago:Abstraction100002137 yago:Group100031264 yago:Class107997703 yago:WikicatProbabilisticComplexityClasses
rdfs:label
Arthur–Merlinプロトコル Protocole Arthur-Merlin AM (Complexitat) Arthur–Merlin protocol Protocolo de Arthur-Merlin Protocolo Arthur-Merlin
rdfs:comment
計算複雑性理論におけるArthur–Merlinプロトコル(Arthur–Merlin protocol)あるいは、Merlin–Arthurプロトコル(Merlin–Arthur protocol)は、検証者のコイン投げが公開されている(使用する乱数が証明者に知られている)タイプの対話型証明プロトコルである。そのようなプロトコルを持つ言語のクラスとして、AM及びMAがそれぞれ定義され、本項では主にこのクラスについて説明する。によって導入された。 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 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. 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. 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. 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.
foaf:depiction
n23:Arthur-Merlin_classes_diagram.svg
dcterms:subject
dbc:Randomized_algorithms
dbo:wikiPageID
663203
dbo:wikiPageRevisionID
1019522025
dbo:wikiPageWikiLink
dbr:Zero_knowledge_proof n10:Arthur-Merlin_classes_diagram.svg dbr:Extended_Riemann_hypothesis dbr:Interactive_proof_system dbr:Sipser–Lautemann_theorem dbr:Cambridge_University_Press n18:poly dbr:Decision_problem dbr:PP_(complexity) dbr:Random_number_generation dbr:QMA dbr:S2P_(complexity) dbr:Formal_language dbr:PSPACE dbr:Complexity_class dbr:Graph_isomorphism_problem dbr:Polynomial_hierarchy dbr:NP_(complexity) dbr:Advice_(complexity) dbc:Randomized_algorithms dbr:IP_(complexity) dbr:Oracle_(computer_science) dbr:BPP_(complexity) n9:poly dbr:Computational_complexity_theory
dbo:wikiPageExternalLink
n22: n27:
owl:sameAs
freebase:m.030v3k dbpedia-ca:AM_(Complexitat) dbpedia-fr:Protocole_Arthur-Merlin wikidata:Q4800823 dbpedia-ja:Arthur–Merlinプロトコル n21:4S9Ct dbpedia-es:Protocolo_Arthur-Merlin dbpedia-pt:Protocolo_de_Arthur-Merlin
dbp:wikiPageUsesTemplate
dbt:ComplexityClasses dbt:Su dbt:More_citations_needed dbt:Frac dbt:Citation dbt:Short_description dbt:Reflist dbt:Harvtxt dbt:CZoo
dbo:thumbnail
n23:Arthur-Merlin_classes_diagram.svg?width=300
dbp:b
2
dbp:p
P
dbo:abstract
計算複雑性理論におけるArthur–Merlinプロトコル(Arthur–Merlin protocol)あるいは、Merlin–Arthurプロトコル(Merlin–Arthur protocol)は、検証者のコイン投げが公開されている(使用する乱数が証明者に知られている)タイプの対話型証明プロトコルである。そのようなプロトコルを持つ言語のクラスとして、AM及びMAがそれぞれ定義され、本項では主にこのクラスについて説明する。によって導入された。 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. 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. 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. 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. 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.
gold:hypernym
dbr:System
prov:wasDerivedFrom
wikipedia-en:Arthur–Merlin_protocol?oldid=1019522025&ns=0
dbo:wikiPageLength
12410
foaf:isPrimaryTopicOf
wikipedia-en:Arthur–Merlin_protocol
Subject Item
dbr:Merlin-Arthur_protocol
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
dbo:wikiPageRedirects
dbr:Arthur–Merlin_protocol
Subject Item
dbr:MA_(complexity)
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
dbo:wikiPageRedirects
dbr:Arthur–Merlin_protocol
Subject Item
dbr:IP_(complexity)
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:Shlomo_Moran
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:Unknotting_problem
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
Subject Item
dbr:Arthur-Merlin
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
dbo:wikiPageRedirects
dbr:Arthur–Merlin_protocol
Subject Item
dbr:CoAM
dbo:wikiPageWikiLink
dbr:Arthur–Merlin_protocol
dbo:wikiPageRedirects
dbr:Arthur–Merlin_protocol
Subject Item
wikipedia-en:Arthur–Merlin_protocol
foaf:primaryTopic
dbr:Arthur–Merlin_protocol