Pytania otagowane jako interactive-proof-systems

1
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 …
2
Interaktywne dowody dla CoNP
Próbuję zrozumieć interaktywne systemy dowodowe i jako ćwiczenie wypróbowałem następujący problem. Wiemy toP.H.⊆ P.S.P.A C.miPH⊆PSPACEPH \subseteq PSPACE i jaP.= PS.P.A C.miIP=PSPACEIP=PSPACE, więc opracuj (łatwe do zrozumienia) interaktywne systemy próbne dla P.H.PHPH? Interaktywny system proof dla N.P.NPNP jest banalna, ale nie udało mi się nawet uzyskać interaktywnego systemu dowodowego c o …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.