Graph Isomorphism is Low for PP
Johannes Köbler, Uwe Schöning, and Jacobo Toran
Abstract:
We show that the graph isomorphism problem is low for PP and for C=P, i.e., it does not provide a PP or C=P computation with any additional power when used as an oracle. Furthermore, we show that graph isomorphism belongs to the class LWPP. A similar result holds for the (apparently more difficult) problem Group Factorization. The problem of determining whether a given graph has a nontrivial automorphism, Graph Automorphism, is shown to be in SPP, and is therefore low for PP, C=P, and ModkP.
Ps-File: Graph Isomorphism is Low for PP