Schnorr trivial sets and truth-table reducibility

Simple item page
dc.contributor.authorFRANKLIN, Johanna N. Y.en_US
dc.contributor.authorSTEPHAN, Franken_US
dc.date.accessioned2008-11-20T09:12:02Zen_US
dc.date.accessioned2017-01-23T07:00:09Z
dc.date.available2008-11-20T09:12:02Zen_US
dc.date.available2017-01-23T07:00:09Z
dc.date.issued2008-03-04en_US
dc.description.abstractIn 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.en_US
dc.format.extent246006 bytesen_US
dc.format.mimetypeapplication/pdfen_US
dc.identifier.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/2821en_US
dc.language.isoenen_US
dc.relation.ispartofseriesTRA3/08en_US
dc.titleSchnorr trivial sets and truth-table reducibilityen_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TRA3-08 - Frank Stephan and Johanna N. Y. Franklin.pdf
Size:
240.24 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.53 KB
Format:
Plain Text
Description:
Download
Collections
Technical Reports