Graph Automorphism and Circuit Size
summary
Shows Graph Automorphism in ZPP relative to the KT/ MKT oracle by reducing rigid-instance isomorphism to a KT-complexity gap: encode T random permutations into a string Z so that non-isomorphic rigid graphs make Z have KT complexity at least T + T S while isomorphic cases allow an M^2 + T S description. The reduction yields a BPP-style extension but fails for standard MCSP because realistic circuit models cannot simulate the KT multiplexer without losing the gap.
AI-written summary · about