Researcher ORCID Identifier
0000-0002-3747-0220
Graduation Year
2022
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Nicholas Pippenger
Reader 2
Arthur T. Benjamin
Terms of Use & License Information
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 4.0 License.
Rights Information
@2022 Kye W Shi
Abstract
In the first half of this thesis, we explore the polynomial-time hierarchy, emphasizing an intuitive perspective that associates decision problems in the polynomial hierarchy to combinatorial games with fixed numbers of turns. Specifically, problems in π are thought of as 0-turn games, ππ as 1-turn βpuzzleβ games, and in general πΊβπ as π-turn games, in which decision problems answer the binary question, βcan the starting player guarantee a win?β We introduce the formalisms of the polynomial hierarchy through this perspective, alongside definitions of π-turn CIRCUIT SATISFIABILITY games, whose πΊβπ-completeness is assumed from prior work (we briefly justify this assumption on intuitive grounds, but no proof is given).
In the second half, we introduce and explore the properties of a novel family of games called the π-turn GRAPH 3-COLORABILITY games. By embedding boolean circuits in proper graph 3-colorings, we construct reductions from π-turn CIRCUIT SATISFIABILITY games to π-turn 3-COLORABILITY games, thereby showing that π-turn 3-COLORABILITY is πΊβπ-complete
Finally, we conclude by discussing possible future generalizations of this work, vis-aΜ-vis extending arbitrary ππ-complete puzzles to interesting πΊβπ-complete games.
Recommended Citation
Shi, Kye, "Games for One, Games for Two: Computationally Complex Fun for Polynomial-Hierarchical Families" (2022). HMC Senior Theses. 259.
https://scholarship.claremont.edu/hmc_theses/259
Comments
https://github.com/kwshi/hmc-ph-thesis