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 Tor′an, showing that DET AC0 -reduces to the rigid graph isomorphism problem, and then appealing to the “Gap Theorem” of [1]. 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.
展开▼
