How hard are sparse sets?
Lane A. Hemachandra, Mitsunori Ogiwara, Osamu Watanabe · 2003
The frontier of knowledge about the structural properties of sparse sets is explored. A collection of topics that are related to the issue of how hard or easy sparse sets is surveyed. The strongest currently known results, together with the open problems that the results leave, are presented.>