Schnorr trivial sets and truth-table reducibility
No Thumbnail Available
Date
2008-03-04
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this paper, we give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations enable us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey, Griffiths and LaForte.