{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/30770"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/30770","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"On The Complexity Of Mathematical Problems: Medvedev Degrees And Reverse Mathematics","abstract":"We investigate the complexity of mathematical problems from two perspectives: Medvedev degrees and reverse mathematics. In the Medvedev degrees, we calculate the complexity of its first-order theory, and we also calculate the complexities of the first-order theories of several related structures. We characterize the join-irreducible Medvedev degrees and deduce several consequences for the interpretation of propositional logic in the Medvedev degrees. We equate the size of chains of Medvedev degrees with the size of chains of sets of reals under ⊆. In reverse mathematics, we analyze the strength of classical theorems of finite graph theory generalized to the countable. In particular, we consider Menger's theorem, Birkhoff's theorem, and unfriendly partitions.","abstract_html":"We investigate the complexity of mathematical problems from two perspectives: Medvedev degrees and reverse mathematics. In the Medvedev degrees, we calculate the complexity of its first-order theory, and we also calculate the complexities of the first-order theories of several related structures. We characterize the join-irreducible Medvedev degrees and deduce several consequences for the interpretation of propositional logic in the Medvedev degrees. We equate the size of chains of Medvedev degrees with the size of chains of sets of reals under ⊆. In reverse mathematics, we analyze the strength of classical theorems of finite graph theory generalized to the countable. In particular, we consider Menger&#x27;s theorem, Birkhoff&#x27;s theorem, and unfriendly partitions.","abstract_has_math":false,"creators":["Shafer, Paul"],"institution":"Cornell University","degree_name":"Ph. D., Mathematics","degree_level":"Doctor of Philosophy","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":["Shore, Richard A"],"committee_members":["Nerode, Anil","Kozen, Dexter Campbell"],"year":2011,"date_issued":"2011-08-31","date_published":"2011-08-31","updated_at":"2026-11-19T03:15:03Z","subjects":["mass problems","Medvedev degrees","reverse mathematics"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["7955521"],"render_values":[{"text":"7955521","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/30770","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/30770","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F30770","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.chair","label":"Chair","values":["Shore, Richard A"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Nerode, Anil","Kozen, Dexter Campbell"]},{"key":"dc:creator","label":"Author","values":["Shafer, Paul"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2012-12-17T13:53:11Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2012-12-17T13:53:11Z"]},{"key":"dc:date.issued","label":"Date","values":["2011-08-31"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctor of Philosophy"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D., Mathematics"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["mass problems","Medvedev degrees","reverse mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["7955521"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/30770"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"2a692951-aec0-46e8-8495-00f5b5a649b1\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>On The Complexity Of Mathematical Problems: Medvedev Degrees And Reverse Mathematics</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2011-08-31</PublicationDate> <Authors> <Author> <DisplayName>Shafer, Paul</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>mass problems</Keyword> <Keyword>Medvedev degrees</Keyword> <Keyword>reverse mathematics</Keyword> <Abstract>We investigate the complexity of mathematical problems from two perspectives: Medvedev degrees and reverse mathematics. In the Medvedev degrees, we calculate the complexity of its first-order theory, and we also calculate the complexities of the first-order theories of several related structures. We characterize the join-irreducible Medvedev degrees and deduce several consequences for the interpretation of propositional logic in the Medvedev degrees. We equate the size of chains of Medvedev degrees with the size of chains of sets of reals under ⊆. In reverse mathematics, we analyze the strength of classical theorems of finite graph theory generalized to the countable. In particular, we consider Menger's theorem, Birkhoff's theorem, and unfriendly partitions.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Shafer, Paul"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["We investigate the complexity of mathematical problems from two perspectives: Medvedev degrees and reverse mathematics. In the Medvedev degrees, we calculate the complexity of its first-order theory, and we also calculate the complexities of the first-order theories of several related structures. We characterize the join-irreducible Medvedev degrees and deduce several consequences for the interpretation of propositional logic in the Medvedev degrees. We equate the size of chains of Medvedev degrees with the size of chains of sets of reals under ⊆. In reverse mathematics, we analyze the strength of classical theorems of finite graph theory generalized to the countable. In particular, we consider Menger's theorem, Birkhoff's theorem, and unfriendly partitions."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["On The Complexity Of Mathematical Problems: Medvedev Degrees And Reverse Mathematics"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"2a692951-aec0-46e8-8495-00f5b5a649b1\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>On The Complexity Of Mathematical Problems: Medvedev Degrees And Reverse Mathematics</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2011-08-31</PublicationDate> <Authors> <Author> <DisplayName>Shafer, Paul</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>mass problems</Keyword> <Keyword>Medvedev degrees</Keyword> <Keyword>reverse mathematics</Keyword> <Abstract>We investigate the complexity of mathematical problems from two perspectives: Medvedev degrees and reverse mathematics. In the Medvedev degrees, we calculate the complexity of its first-order theory, and we also calculate the complexities of the first-order theories of several related structures. We characterize the join-irreducible Medvedev degrees and deduce several consequences for the interpretation of propositional logic in the Medvedev degrees. We equate the size of chains of Medvedev degrees with the size of chains of sets of reals under ⊆. In reverse mathematics, we analyze the strength of classical theorems of finite graph theory generalized to the countable. In particular, we consider Menger's theorem, Birkhoff's theorem, and unfriendly partitions.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Shafer, Paul"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:contributor.chair":["Shore, Richard A"],"dc:contributor.committeemember":["Nerode, Anil","Kozen, Dexter Campbell"],"dc:creator":["Shafer, Paul"],"dc:date.accessioned":["2012-12-17T13:53:11Z"],"dc:date.available":["2012-12-17T13:53:11Z"],"dc:date.issued":["2011-08-31"],"dc:description.abstract":["We investigate the complexity of mathematical problems from two perspectives: Medvedev degrees and reverse mathematics. In the Medvedev degrees, we calculate the complexity of its first-order theory, and we also calculate the complexities of the first-order theories of several related structures. We characterize the join-irreducible Medvedev degrees and deduce several consequences for the interpretation of propositional logic in the Medvedev degrees. We equate the size of chains of Medvedev degrees with the size of chains of sets of reals under ⊆. In reverse mathematics, we analyze the strength of classical theorems of finite graph theory generalized to the countable. In particular, we consider Menger's theorem, Birkhoff's theorem, and unfriendly partitions."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["7955521"],"dc:identifier.uri":["https://hdl.handle.net/1813/30770"],"dc:language.iso":["en_US"],"dc:subject":["mass problems","Medvedev degrees","reverse mathematics"],"dc:title":["On The Complexity Of Mathematical Problems: Medvedev Degrees And Reverse Mathematics"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Doctor of Philosophy"],"thesis:degree_name":["Ph. D., Mathematics"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-11-19T03:15:03Z"}