Eu li em SP Jordan, D. Gosset, "PJ Amor -Complete problemas para Hamiltonians stoquastic e matrizes de Markov " que é improvável que .
Fiquei surpreso com essa afirmação. Então, qual é a relação adequada entre e A M ?
Eu li em SP Jordan, D. Gosset, "PJ Amor -Complete problemas para Hamiltonians stoquastic e matrizes de Markov " que é improvável que .
Fiquei surpreso com essa afirmação. Então, qual é a relação adequada entre e A M ?
Respostas:
Sabe-se que não há relação entre QMA e AM, e é razoável supor que eles são incomparáveis.
Se o QMA for provado estar contido no AM, seria um resultado absolutamente enorme na complexidade quântica. É claro que isso implicaria que o BQP está no PH, o que seria enorme, mas iria além disso - certamente exigiria grandes revelações sobre a estrutura dos algoritmos e certificados quânticos.
Dito isto, a evidência contra não é muito convincente. Um oráculo em relação ao qual o QMA não está contido no AM ajudaria, e parece que esse resultado pode não estar muito distante - mas ainda nem o temos.
Uma prova da contenção reversa, AM no QMA, também seria enorme. Pelo menos aqui temos um oráculo em relação ao qual AM não está contido no QMA (e, de fato, nem mesmo está contido no PP).
fonte
Apenas uma coisa a acrescentar à resposta de John:
Sob uma hipótese plausível de derandomização, AM = NP. Nesse caso, certamente teríamos AM ⊆ QMA.
fonte