Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR15-162 | 16th February 2018 21:14

A note on Graph Automorphism and Smart Reductions


Revision #1
Authors: Eric Allender, Joshua Grochow, Cris Moore, Dieter van Melkebeek, Andrew Morgan
Accepted on: 16th February 2018 21:14
Downloads: 1038


It is well-known that the complexity of the Graph Automorphism problem is characterized by a special case of Graph Isomorphism, where the input graphs satisfy the "promise" of being rigid (that is, having no nontrivial automorphisms). In this brief note, we observe that the reduction of Graph Automorphism to the Rigid Graph Isomorphism problem can be accomplished even using Grollman and Selman's notion of a "smart reduction".

Changes to previous version:

The "old" TR15-162 is now subsumed by TR17-158. This "revision" consists of an orphan theorem.


TR15-162 | 9th October 2015 04:02

Graph Isomorphism and Circuit Size


We show that the Graph Automorphism problem is ZPP-reducible to MKTP, the problem of minimizing time-bounded Kolmogorov complexity. MKTP has previously been studied in connection with the Minimum Circuit Size Problem (MCSP) and is often viewed as essentially a different encoding of MCSP. All prior reductions to MCSP have applied equally well to MKTP, and vice-versa, and all such reductions have relied on the fact that functions computable in polynomial time can be inverted with high probability relative to MCSP and MKTP. Our reduction uses a different approach, and consequently yields the first example of a problem in ZPP$^{\rm MKTP}$ that is not known to lie in NP $\cap$ coNP. We also show that this approach can be used to provide a reduction of the Graph Isomorphism problem to MKTP.

ISSN 1433-8092 | Imprint