NP-hard sets are superterse unless NP is small

Introduction One of the important questions in computational complexity theory is whether every NP problem is solvable by polynomial time circuits, i.e., NP `?P=poly. Furthermore, it has been asked what the deterministic time complexity of NP is if NP ` P=poly. That is, if NP is easy in the nonuniform complexity measure, how easy is NP in the uniform complexity measure? Let P T (SPARSE) be the class of languages that are polynomial time Turing reducible to some sparse sets. Then it is well known that P T (SPARSE) = P=poly. Hence the above question is equivalent to the following question. NP `?PT (SPARSE): It has been shown by Wilson [18] that th