<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/xsl'?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T09:57:34Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/30770" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/30770</identifier><datestamp>2026-05-14T13:53:02Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en_US">Shafer, Paul</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="chair" lang="en_US">Shore, Richard A</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Nerode, Anil</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember" lang="en_US">Kozen, Dexter Campbell</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2012-12-17T13:53:11Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2012-12-17T13:53:11Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en_US">2011-08-31</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/30770</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">7955521</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">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.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en_US">en_US</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">mass problems</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Medvedev degrees</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">reverse mathematics</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">On The Complexity Of Mathematical Problems:  Medvedev Degrees And Reverse Mathematics</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="discipline">Mathematics</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="grantor" lang="en_US">Cornell University</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="level">Doctor of Philosophy</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="name">Ph. D., Mathematics</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://cornell-ecommons.eks.prod.4science.cloud/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author" lang="en_US">Shafer, Paul</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="2a692951-aec0-46e8-8495-00f5b5a649b1">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en_US&lt;/Language>
   	&lt;Title>On The Complexity Of Mathematical Problems:  Medvedev Degrees And Reverse Mathematics&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2011-08-31&lt;/PublicationDate>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Shafer, Paul&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;Keyword>mass problems&lt;/Keyword>
    &lt;Keyword>Medvedev degrees&lt;/Keyword>
    &lt;Keyword>reverse mathematics&lt;/Keyword>
   	&lt;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&amp;apos;s theorem, Birkhoff&amp;apos;s theorem, and unfriendly partitions.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>