Back to search

Cornell University

On The Complexity Of Mathematical Problems: Medvedev Degrees And Reverse Mathematics

Abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Mathematics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Mathematics
Grantor
Cornell University
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shafer, Paul
Chair dc:contributor.chair
  • Shore, Richard A
Committee members dc:contributor.committeemember
  • Nerode, Anil
  • Kozen, Dexter Campbell

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
7955521

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shafer, Paul. On The Complexity Of Mathematical Problems: Medvedev Degrees And Reverse Mathematics. Doctor of Philosophy thesis, Cornell University, 2011. https://hdl.handle.net/1813/30770