Arthur–Merlin protocol
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.
Wikipage disambiguates
AI-completeAMAM (complexity)Arthur-MerlinArthur-Merlin protocolBPP (complexity)Circuit complexityCoAMComplexity classComputational complexity theoryDistinguishing coloringGraph isomorphism problemIP (complexity)Interactive proof systemKarp–Lipton theoremLattice problemList of complexity classesList of computability and complexity topicsMAMA (complexity)Merlin-Arthur protocolNP (complexity)P/polyPP (complexity)Polynomial-time reductionQMAS2P (complexity)Shlomo MoranSipser–Lautemann theoremStathis ZachosTime complexityTrue quantified Boolean formulaUnknotting problem
Link from a Wikipage to another Wikipage
primaryTopic
Arthur–Merlin protocol
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.
has abstract
En la teoría de complejidad co ...... ar sus decisiones y consultas.
@es
En teoria de la complexitat, l ...... orfs pertany a aquesta classe.
@ca
En théorie de la complexité, u ...... actives avec aléatoire public.
@fr
In computational complexity th ...... ake its decisions and queries.
@en
Na área da Complexidade comput ...... mar suas decisões e consultas.
@pt
計算複雑性理論におけるArthur–Merlinプロトコル( ...... 本項では主にこのクラスについて説明する。によって導入された。
@ja
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,019,522,025
Link from a Wikipage to another Wikipage
p
P
@en
wikiPageUsesTemplate
subject
hypernym
comment
En la teoría de complejidad co ...... ractivas con monedas públicas.
@es
En teoria de la complexitat, l ...... mb probabilitat d'almenys 2/3.
@ca
En théorie de la complexité, u ...... actives avec aléatoire public.
@fr
In computational complexity th ...... tive proofs with public coins.
@en
Na área da Complexidade comput ...... terativas com moedas públicas.
@pt
計算複雑性理論におけるArthur–Merlinプロトコル( ...... 本項では主にこのクラスについて説明する。によって導入された。
@ja
label
AM (Complexitat)
@ca
Arthur–Merlin protocol
@en
Arthur–Merlinプロトコル
@ja
Protocole Arthur-Merlin
@fr
Protocolo Arthur-Merlin
@es
Protocolo de Arthur-Merlin
@pt