ON THE COMPUTATIONAL-COMPLEXITY OF SMALL DESCRIPTIONS

For a set L that is polynomial-time reducible (in short, less than or equal to(T)(P)-reducible) to some sparse set, the authors investigate the computational complexity of such sparse sets relative to L and pro ve the first lower bounds on the complexity of recognizing such sets. Sets A and B are constructed such that both of them are less than or e qual to(T)(P)-reducible to some sparse set, but A (respectively, B) is less than or equal to(T)(P)-reducible to no sparse set in P-A (respec tively, NPB boolean AND co-NPB); that is, the complexity of sparse set s to which A (respectively, B) is less than or equal to(T)(P)-reducibl e is more than P-A (respectively, NPB boolean AND co-NPB). From these results or application of the proof technique the authors obtain (1) l ower 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.