Abstract:
We show that every problem in the complexity class (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (). In particular Graph Isomorphism lies in .
This is the first theorem relating the computational power of Graph Isomorphism and , despite the long history these problems share, as candidate -intermediate problems.