##
**On the computational complexity of small descriptions.**
*(English)*
Zbl 0799.68085

Summary: For a set \(L\) that is polynomial-time reducible (in short, \(\leq^ P_ T\)-reducible) to some sparse set, the authors investigate the computational complexity of such sparse sets relative to \(L\) and prove the first lower bounds on the complexity of recognizing such sets. Sets \(A\) and \(B\) are constructed such that both of them are \(\leq^ P_ T\)- reducible to some sparse set, but \(A\) (respectively, \(B\)) is \(\leq^ P_ T\)-reducible to no sparse set in \(P^ A\) (respectively, \(\text{NP}^ B\cap\text{co-NP}^ B\)); that is, the complexity of sparse sets to which \(A\) (respectively, \(B\)) is \(\leq^ P_ T\)-reducible is more than \(P^ A\) (respectively, \(\text{NP}^ B\cap\text{co-NP}^ B\)). From these results or application of the proof technique the authors obtain (1) lower bounds for the relative complexity of generating polynomial-size circuits for some sets in \(P\)/poly and (2) separations of the classes of sets equivalent or reducible to sparse sets under various polynomial-time reducibilities.

### MSC:

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |

68Q25 | Analysis of algorithms and problem complexity |