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 AM opiera się na losowych redukcjach do 3SAT zamiast na redukcjach Karp, których używamy do deterministycznych klas złożoności. Może więc, skoro redukcje Karpa nie zawierają błędu, „Karp redukujący się do problemu AM” nie ma tak naprawdę żadnego znaczenia, tym samym unieważniając zwykłe pojęcie, że używamy „pełnego” problemu?
complexity-theory
reductions
complexity-classes
interactive-proof-systems
LinearZoetrope
źródło
źródło
Odpowiedzi:
źródło