- A Note on the Relationship between the
Determinant and Time-Bounded Kolmogorov
Complexity
- Project Year:
2019
- REU Student (s):
Azucena Garvia-Bosshard | University of Edinburgh
| Amulya Musipatla | Carnegie Mellon University PA
- Student 1 Institution:
University of Edinburgh
- Student 2 Institution:
Carnegie Mellon University
- Project Mentor:
Eric Allender
- Project Mentor Area:
Computer Science
- Project Abstract:
Our work focused on a variant of the circuit
minimization problem (MCSP), denoted MKTP, which studies
resource-bounded Kolmogorov complexity in place of circuit
size. These problems have gained attention as promising candidates
for NP-intermediate problems. We show that MKTP
and Graph Isomorphism (GI) are hard for the class DET via
nonuniform projections. Previous results have proven hardness
under logspace reductions and nonuniform NC0 reductions, our
paper strengthens these results.
