Pytania oznaczone «interactive-proof-systems»

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...

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...