Czy izomorfizm grafów występuje w UP coUP?

Czy izomorfizm grafów (problem decyzyjny) znajduje się w ? Tutaj to klasa problemów decyzyjnych akceptowanych przez jednoznaczną maszynę Turinga (patrz zoo złożoności ). $\mathsf{UP}\cap \mathsf{coUP}$ $\mathsf{UP}$

cc.complexity-theory graph-isomorphism Fayez Abdlrazaq Deab
źródło

Wykres izomorfizm jest w UP. Jednak i nie wiemy, czy izomorfizm grafów jest w , więc odpowiedź brzmi: nie wiemy.

c o U P \subseteq c o N P

$coUP \subseteq coNP$

c o N P

$coNP$

Peter Shor,

Czy mogę uzyskać odniesienie do izomorfizmu grafów w UP?

sdcvvc,

@PeterShor: Miałem wrażenie, że GI nie było znane z UP ... Zestaw izomorfizmów między dwoma wykresami ma liczność równą 0 lub równą wielkości grupy automorfizmów jednego z wykresów, więc „naturalny „Algorytm NP z pewnością nie jest algorytmem UP. Czy miałeś na myśli jakiś inny niedeterministyczny algorytm dla GI, który jest algorytmem UP?

Joshua Grochow,

@Joshua: masz rację. GI nie jest znane z UP.

Peter Shor,

GI znajduje się przynajmniej w SZK, statystycznej klasie zerowej wiedzy; w znanych pojemnikach jest zatem także w AM, coAM i coNP / poli (coAM jest w coNP / poli przez standardową niejednorodną derandomizację). Na przykład ten dokument omawia znane górne granice SZK: cs.ucla.edu/~sahai/work/web/2003%20Publications/J.ACM2003.pdf

Andy Drucker

Odpowiedzi:

Wykres izomorfizm nie jest znany w ani w . $\mathsf{UP}$ $\mathsf{coUP}$

Dla : naturalny niedeterministyczny algorytm - zgadnij mapę między dwoma wykresami i sprawdź, czy jest to izomorfizm - ma 0 świadków (jeśli wykresy nie są izomorficzne) lubświadkowie. Chociaż większość wykresów ma (to znaczy, jeśli wybierzesz losowy wykres na wierzchołkach, prawdopodobieństwo, że ma jakieś nietrywialne automorfizmy, szybko wzrasta do przy ), to nie jest wystarczy powiedzieć, że zawsze jest co najwyżej jeden świadek. To oczywiście nie wyklucza innych algorytmów, które mogłyby pokazywać, że izomorfizm grafów w . (W końcu możliwe jest, że występuje izomorfizm grafów $\mathsf{UP}$ $|\text{Aut}(G)|$ $|\text{Aut}(G)|=1$ $n$ $0$ $n$ $\mathsf{UP}$ $\mathsf{P} \subseteq \mathsf{UP}$ ).

Jeśli chodzi o , jak zauważył Peter Shor, nie wiemy nawet, czy izomorfizm grafów jest w , więc na pewno nie wiemy, czy to jest w . (Przy prawdopodobnym założeniu o derandomizacji jest to , ale nie znam żadnego naturalnego założenia, które to w lub .) $\mathsf{coUP}$ $\mathsf{coNP}$ $\mathsf{coUP}$ $\mathsf{coNP}$ $\mathsf{UP}$ $\mathsf{coUP}$

Joshua Grochow
źródło