|
DSpace at School of Computing, NUS >
School of Computing >
Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1900.100/2821
|
| Title: | Schnorr trivial sets and truth-table reducibility |
| Authors: | FRANKLIN, Johanna N. Y.
STEPHAN, Frank |
| Issue Date: | 4-Mar-2008 |
| Series/Report no.: | ;TRA3/08 |
| 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. |
| URI: | http://hdl.handle.net/1900.100/2821 |
| Appears in Collections: | Technical Reports
|
Files in This Item:
| File |
Size | Format |
|---|
| TRA3-08 - Frank Stephan and Johanna N. Y. Franklin.pdf | 240Kb | Adobe PDF | View/Open |
|
Show full item record
All items in DSpace are protected by copyright, with all rights reserved.
|
