Show simple item record

dc.contributor.authorShafer, Paulen_US
dc.identifier.otherbibid: 7955521
dc.description.abstractWe 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.en_US
dc.subjectmass problemsen_US
dc.subjectMedvedev degreesen_US
dc.subjectreverse mathematicsen_US
dc.titleOn The Complexity Of Mathematical Problems: Medvedev Degrees And Reverse Mathematicsen_US
dc.typedissertation or thesisen_US Universityen_US of Philosophy D., Mathematics
dc.contributor.chairShore, Richard Aen_US
dc.contributor.committeeMemberNerode, Anilen_US
dc.contributor.committeeMemberKozen, Dexter Campbellen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record