Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-158 | 26th October 2020 22:59

A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity



This paper focuses on a variant of the circuit minimization problem (MCSP), denoted MKTP, which studies resource-bounded Kolmogorov complexity in place of circuit size. MCSP is not known to be hard for any complexity class under any kind of m-reducibility, but recently MKTP was shown to be hard for DET under m-reductions computable in NC0, by presenting an AC0 reduction from the rigid graph isomorphism problem to MKTP, and combining that with a theorem of Toran, showing that DET AC0-reduces to the rigid graph isomorphism problem, and then appealing to the "Gap Theorem" of [Agrawal, Allender, Rudich]. Here, we show that these reductions can be accomplished by means of projections. Thus MKTP is hard for DET under projections, and the rigid graph isomorphism problem is hard for DET under uniform projections.

ISSN 1433-8092 | Imprint