Y a-t-il des problèmes AM-complete connus / AM-complete est-il bien défini?

Je suis curieux de savoir s'il existe des problèmes complets dans la classe de complexité Arthur-Merlin. Le graphique de non-isomorphisme (GNI) semble être l'exemple canonique d'un problème en AM, mais ce n'est probablement pas complet.

Je suppose que je me demande aussi si un problème "complet" est bien défini pour AM. Puisque AM = BP.NP, il semble que le passage à la "réduction" en AM repose sur des réductions aléatoires vers 3SAT plutôt que sur les réductions de Karp que nous utilisons pour les classes de complexité déterministes. Alors peut-être que puisque les réductions de Karp n'ont pas d'erreur, «la réduction de Karp à un problème AM» n'a pas vraiment de sens, invalidant ainsi la notion habituelle que nous utilisons d'un problème «complet»?

Puisque AM = BP.NP, il semble que le passage à la "réduction" en AM repose sur des réductions aléatoires vers 3SAT plutôt que sur les réductions de Karp que nous utilisons pour les classes de complexité déterministes.

C'est une mauvaise intuition. Quelle que soit la façon dont vous définissez votre classe de complexité , s'il existe un problème tel que pour chaque problème , vous ont , alors est un problème complet à plusieurs reprises de .$\mathbb{C}$$\mathrm{A}\in \mathbb{C}$$\mathrm{B}\in \mathbb{C}$$\mathrm{B} \leq_p \mathrm{A}$$\mathrm{A}$$\mathbb{C}$

En fait, même un problème qui est complété par des réductions aléatoires pour n'est pas connu. En d'autres termes, il semble très difficile de simplement identifier un problème de décision particulier dans afin que nous puissions avoir une réduction non triviale d'autres problèmes connus pour être dans .$\mathrm{AM}$$\mathrm{AM}$A M$\mathrm{AM}$

Voir mathoverflow.net/questions/34469 et cstheory.stackexchange.com/questions/1233; en bref, la définition de la MA repose sur une promesse, ce qui rend difficile la définition d'une réduction. - sdcvvc

C'est l'un des obstacles sur le chemin pour trouver un problème complet pour . Cela s'applique également à , , - , . Ces classes nécessitent que la machine de Turing probabiliste poly-temps ait une probabilité d'erreur limitée sur toutes les instances. La situation est beaucoup plus facile pour , cette classe ne met aucune exigence sur la probabilité d'erreur, quel que soit le résultat ayant la probabilité la plus élevée est la réponse de la machine afin que nous puissions facilement attraper un problème complet, à savoir - .$\mathrm{AM}$$\mathrm{BPP}$$\mathrm{RP}$$\mathrm{co}$$\mathrm{RP}$$\mathrm{ZPP}$$\mathrm{PP}$$\mathrm{MAJ}$$\mathrm{SAT}$