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.


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
Full Text: DOI Link