{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/86960"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/86960","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Abstract Complexity Theory and the Degrees of Unsolvability","abstract":"We focus on the A° sets and show that abstract complexity theory can be applied to the degrees of unsolvability simply by relativizing the notion of a complexity measure to 0'. Since the Gap Theorem holds in our context, we need to develop the concept of a A° honest function just as one needs to define honest functions in computational complexity theory. These functions turn out to be the appropriate complexity bounds, and the concept enables us to prove general hierarchy results for A° sets. Since we must often deal with noncomputable complexity bounds, we develop a hierarchy of A° functions, the compositon hierarchy, to classify those functions that have relatively simple computable approximations. The degrees in L2 have especially pleasant complexity theoretic properties, and w ithin this context we use the composition hierarchy to formulate and prove hierarchy results for c.e. degrees, generic degrees, and a n c degrees. Furthermore, the degrees in $ {L\\sb1}.$and those in $ {L\\sb2}.$ — $ {L\\sb1}.$are seen to have m any complexity theoretic properties in common. In addition, we develop several variations on the standard notions of genericity, including one, semigenericity, that can be satisfied by sets in $\\overline{L\\sb1}.$ Finally, we prove results indicating how complexity theoretic considerations can lead to structural consequences in the degrees.","abstract_html":"We focus on the A° sets and show that abstract complexity theory can be applied to the degrees of unsolvability simply by relativizing the notion of a complexity measure to 0'. Since the Gap Theorem holds in our context, we need to develop the concept of a A° honest function just as one needs to define honest functions in computational complexity theory. These functions turn out to be the appropriate complexity bounds, and the concept enables us to prove general hierarchy results for A° sets. Since we must often deal with noncomputable complexity bounds, we develop a hierarchy of A° functions, the compositon hierarchy, to classify those functions that have relatively simple computable approximations. The degrees in L2 have especially pleasant complexity theoretic properties, and w ithin this context we use the composition hierarchy to formulate and prove hierarchy results for c.e. degrees, generic degrees, and a n c degrees. Furthermore, the degrees in $ {L\\sb1}.$and those in $ {L\\sb2}.$ — $ {L\\sb1}.$are seen to have m any complexity theoretic properties in common. In addition, we develop several variations on the standard notions of genericity, including one, semigenericity, that can be satisfied by sets in $\\overline{L\\sb1}.$ Finally, we prove results indicating how complexity theoretic considerations can lead to structural consequences in the degrees.","abstract_has_math":true,"creators":["Schaeffer, Benjamin James"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Carl Jockusch, Jr"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-28T15:20:22Z","date_published":"2015-09-28T15:20:22Z","updated_at":"2026-07-22T22:26:28Z","subjects":["Mathematics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI9834765"],"render_values":[{"text":"(MiAaPQ)AAI9834765","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/86960","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Carl Jockusch, Jr"]},{"key":"dc:creator","label":"Author","values":["Schaeffer, Benjamin James"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-28T15:20:22Z","10000-01-01","1998"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/86960","(MiAaPQ)AAI9834765"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We focus on the A° sets and show that abstract complexity theory can be applied to the degrees of unsolvability simply by relativizing the notion of a complexity measure to 0'. Since the Gap Theorem holds in our context, we need to develop the concept of a A° honest function just as one needs to define honest functions in computational complexity theory. These functions turn out to be the appropriate complexity bounds, and the concept enables us to prove general hierarchy results for A° sets. Since we must often deal with noncomputable complexity bounds, we develop a hierarchy of A° functions, the compositon hierarchy, to classify those functions that have relatively simple computable approximations. The degrees in L2 have especially pleasant complexity theoretic properties, and w ithin this context we use the composition hierarchy to formulate and prove hierarchy results for c.e. degrees, generic degrees, and a n c degrees. Furthermore, the degrees in $ {L\\sb1}.$and those in $ {L\\sb2}.$ — $ {L\\sb1}.$are seen to have m any complexity theoretic properties in common. In addition, we develop several variations on the standard notions of genericity, including one, semigenericity, that can be satisfied by sets in $\\overline{L\\sb1}.$ Finally, we prove results indicating how complexity theoretic considerations can lead to structural consequences in the degrees.","Made available in DSpace on 2015-09-28T15:20:22Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 9834765.pdf: 7778717 bytes, checksum: 136154b7b460e027edab087521fe267a (MD5) Previous issue date: 1998","Embargo set by: Seth Robbins for item 88241 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","168 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1998."]},{"key":"dc:title","label":"Title","values":["Abstract Complexity Theory and the Degrees of Unsolvability"]}]}],"canonical_facts":{"dc:contributor":["Carl Jockusch, Jr"],"dc:creator":["Schaeffer, Benjamin James"],"dc:date":["2015-09-28T15:20:22Z","10000-01-01","1998"],"dc:description":["We focus on the A° sets and show that abstract complexity theory can be applied to the degrees of unsolvability simply by relativizing the notion of a complexity measure to 0'. Since the Gap Theorem holds in our context, we need to develop the concept of a A° honest function just as one needs to define honest functions in computational complexity theory. These functions turn out to be the appropriate complexity bounds, and the concept enables us to prove general hierarchy results for A° sets. Since we must often deal with noncomputable complexity bounds, we develop a hierarchy of A° functions, the compositon hierarchy, to classify those functions that have relatively simple computable approximations. The degrees in L2 have especially pleasant complexity theoretic properties, and w ithin this context we use the composition hierarchy to formulate and prove hierarchy results for c.e. degrees, generic degrees, and a n c degrees. Furthermore, the degrees in $ {L\\sb1}.$and those in $ {L\\sb2}.$ — $ {L\\sb1}.$are seen to have m any complexity theoretic properties in common. In addition, we develop several variations on the standard notions of genericity, including one, semigenericity, that can be satisfied by sets in $\\overline{L\\sb1}.$ Finally, we prove results indicating how complexity theoretic considerations can lead to structural consequences in the degrees.","Made available in DSpace on 2015-09-28T15:20:22Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 9834765.pdf: 7778717 bytes, checksum: 136154b7b460e027edab087521fe267a (MD5) Previous issue date: 1998","Embargo set by: Seth Robbins for item 88241 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","168 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1998."],"dc:identifier":["http://hdl.handle.net/2142/86960","(MiAaPQ)AAI9834765"],"dc:language":["eng"],"dc:subject":["Mathematics"],"dc:title":["Abstract Complexity Theory and the Degrees of Unsolvability"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:28Z"}