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