## Abstract

We continue an investigation of resource-bounded Kolmogorov complexity and de randomization techniques begun in [2, 3]. We introduce nondeterministic time-bounded Kolmogorov complexity measures (KNt and KNT) and examine the properties of these measures using constructions of hitting set generators for nondeterministic circuits. We observe that KNt bears many similarities to the nondeterministic distinguishing complexity C N D of [8]. This motivates the definition of a new notion of time-bounded distinguishing complexity KDt, as an intermediate notion with connections to the class FewEXP. The set of KDt-random strings is complete for EXP under P/poly reductions. Most of the notions of resource-bounded Kolmogorov complexity discussed here and in the earlier papers have close connections to circuit size (on different types of circuits). We extend this framework to define notions of Kolmogorov complexity KB and KF that are related to branching program size and formula size, respectively. The sets of KB- and KF-random strings lie in coNP; we show that oracle access to these sets enables one to factor Blum integers. We obtain related intractability results for approximating minimum formula size, branching program size, and circuit size. The NEXP ⊆ NC^{1} and NEXP ⊆ L/poly questions are shown to be equivalent to conditions about the KF and KB complexity of sets in P.

Original language | English (US) |
---|---|

Pages (from-to) | 209-220 |

Number of pages | 12 |

Journal | Proceedings of the Annual IEEE Conference on Computational Complexity |

State | Published - 2003 |

Event | 18th Annual IEEE Conference on Computational Complexity - Aarhus, Denmark Duration: Jul 7 2003 → Jul 10 2003 |

## All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Computational Mathematics