Existem problemas conhecidos com o AM completo / o AM completo está bem definido?

12

Estou curioso para saber se há algum problema completo na classe de complexidade Arthur-Merlin. Gráfico O não-isomorfismo (RNB) parece ser o exemplo canônico de um problema no AM, mas provavelmente não é completo.

Suponho que também esteja pensando se um problema "completo" está bem definido para AM. Já que AM = BP.NP, parece que a "redução" para AM depende de reduções aleatórias para 3SAT, em vez das reduções de Karp que usamos para classes de complexidade determinística. Então, como as reduções de Karp não têm erro, "Karp reduzindo a um problema de AM" não tem realmente nenhum significado, invalidando assim a noção usual que usamos de um problema "completo"?

LinearZoetrope
fonte
3
Consulte mathoverflow.net/questions/34469 e cstheory.stackexchange.com/questions/1233 ; em suma, a definição de AM depende de uma promessa, e isso torna difícil definir uma redução.
Sdcvvc

Respostas:

0

Já que AM = BP.NP, parece que a "redução" para AM depende de reduções aleatórias para 3SAT, em vez das reduções de Karp que usamos para classes de complexidade determinística.

Esta é uma intuição errada. Independentemente de como você define sua classe de complexidade C , se houver algum problema UMAC tal que, para todo problema BC , você tenha BpUMA , então UMA é um problema de muitos uma completa de C .

UMAMUMAMUMAM

Consulte mathoverflow.net/questions/34469 e cstheory.stackexchange.com/questions/1233; em suma, a definição de AM depende de uma promessa, e isso torna difícil definir uma redução. - sdcvvc

UMAMBPPRPcoRPZPPPPMUMAJSUMAT

Thinh D. Nguyen
fonte