On The Complexity Of Mathematical Problems: Medvedev Degrees And Reverse Mathematics
Loading...
No Access Until
Permanent Link(s)
Collections
Other Titles
Authors
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.
Journal / Series
Volume & Issue
Description
Sponsorship
Date Issued
2011-08-31
Publisher
Keywords
mass problems; Medvedev degrees; reverse mathematics
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Shore, Richard A
Committee Co-Chair
Committee Member
Nerode, Anil
Kozen, Dexter Campbell
Kozen, Dexter Campbell
Degree Discipline
Mathematics
Degree Name
Ph. D., Mathematics
Degree Level
Doctor of Philosophy
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
References
Link(s) to Reference(s)
Previously Published As
Government Document
ISBN
ISMN
ISSN
Other Identifiers
Rights
Rights URI
Types
dissertation or thesis