On the computational complexity of small descriptions
- 10 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
For a set L that is polynomial time reducible to some sparse set, the authors investigate the computational complexity of such sparse sets relative to L. They construct sets A and B such that both of them are polynomial time reducible to some sparse set, but A (resp., B) is polynomial time reducible to no sparse set in P/sup A/ (resp., NP/sup B/ intersection co-NP/sup B/); that is, the complexity of sparse sets to which A (resp., B) is reducible is more than P/sup A/ (resp., NP/sup B/ intersection co-NP/sup B/). From these results and/or application of their proof technique the authors obtain: (1) lower bounds for the relative complexity of finding polynomial size circuits for some sets in P/poly, and (2) separations of the equivalence classes of sparse sets under various reducibilities.Keywords
This publication has 20 references indexed in Scilit:
- Lower bounds for the low hierarchyPublished by Springer Nature ,1989
- Learning regular sets from queries and counterexamplesInformation and Computation, 1987
- Complexity and StructureLecture Notes in Computer Science, 1986
- Continuous optimization problems and a polynomial hierarchy of real functionsJournal of Complexity, 1985
- Computation times of NP sets of different densitiesTheoretical Computer Science, 1984
- Generalized Kolmogorov complexity and the structure of feasible computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Strong nondeterministic polynomial-time reducibilitiesTheoretical Computer Science, 1982
- Some connections between nonuniform and uniform complexity classesPublished by Association for Computing Machinery (ACM) ,1980
- On simultaneous resource boundsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975