Czy są jakieś znane problemy z kompletnym AM / czy kompletne AM jest dobrze zdefiniowane?

Jestem ciekawy, czy w klasie złożoności Arthura-Merlina występują jakieś kompletne problemy. Graph Non-Isomorphism (GNI) wydaje się być kanonicznym przykładem problemu w AM, ale prawdopodobnie nie jest kompletny.

Chyba zastanawiam się również, czy „kompletny” problem jest dobrze zdefiniowany dla AM. Ponieważ AM = BP.NP, wydaje się, że przejście na „redukcję” do AM opiera się na losowych redukcjach do 3SAT zamiast na redukcjach Karp, których używamy do deterministycznych klas złożoności. Może więc, skoro redukcje Karpa nie zawierają błędu, „Karp redukujący się do problemu AM” nie ma tak naprawdę żadnego znaczenia, tym samym unieważniając zwykłe pojęcie, że używamy „pełnego” problemu?

Ponieważ AM = BP.NP, wydaje się, że przejście na „redukcję” do AM opiera się na losowych redukcjach do 3SAT zamiast na redukcjach Karp, których używamy do deterministycznych klas złożoności.

$\mathbb{C}$$\mathrm{A}\in \mathbb{C}$$\mathrm{B}\in \mathbb{C}$$\mathrm{B} \leq_p \mathrm{A}$$\mathrm{A}$$\mathbb{C}$

$\mathrm{AM}$$\mathrm{AM}$$\mathrm{AM}$

Zobacz mathoverflow.net/questions/34469 i cstheory.stackexchange.com/questions/1233; w skrócie, definicja AM opiera się na obietnicy, co utrudnia zdefiniowanie redukcji. - sdcvvc

$\mathrm{AM}$$\mathrm{BPP}$$\mathrm{RP}$$\mathrm{co}$$\mathrm{RP}$$\mathrm{ZPP}$$\mathrm{PP}$$\mathrm{MAJ}$$\mathrm{SAT}$