Reverse mathematics and Weihrauch analysis motivated by finite complexity theory

Article type: Research Article

Authors: BeMent, Zach^{a; *} | Hirst, Jeffry^b | Wallace, Asuka^c

Affiliations: [a] Department of Mathematical Sciences, Appalachian State University, Boone, NC 28608, USA. bementza@appstate.edu | [b] Department of Mathematical Sciences, Appalachian State University, Boone, NC 28608, USA. hirstjl@appstate.edu | [c] Department of Mathematical Sciences, Appalachian State University, Boone, NC 28608, USA. AsukaWallace@gmail.com

Correspondence: [*] Corresponding author. bementza@appstate.edu.

Abstract: We extend a study by Lempp and Hirst of infinite versions of some problems from finite complexity theory, using an intuitionistic version of reverse mathematics and techniques of Weihrauch analysis.

Keywords: Reverse mathematics, Weihrauch, isomorphic subgraph, LPO, ACA, Π¹₁ comprehension

DOI: 10.3233/COM-210310

Journal: Computability, vol. 10, no. 4, pp. 343-354, 2021