ECCC-Report TR15-162https://eccc.weizmann.ac.il/report/2015/162Comments and Revisions published for TR15-162en-usFri, 16 Feb 2018 21:14:26 +0200
Revision 1
| A note on Graph Automorphism and Smart Reductions |
Eric Allender,
Joshua Grochow,
Cris Moore,
Dieter van Melkebeek,
Andrew Morgan
https://eccc.weizmann.ac.il/report/2015/162#revision1It 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".Fri, 16 Feb 2018 21:14:26 +0200https://eccc.weizmann.ac.il/report/2015/162#revision1
Paper TR15-162
| Graph Isomorphism and Circuit Size |
Eric Allender,
Joshua Grochow,
Cris Moore
https://eccc.weizmann.ac.il/report/2015/162We 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.Fri, 09 Oct 2015 04:02:53 +0300https://eccc.weizmann.ac.il/report/2015/162