Kye ShiFollow

Researcher ORCID Identifier


Graduation Year


Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science



Reader 1

Nicholas Pippenger

Reader 2

Arthur T. Benjamin

Terms of Use & License Information

Creative Commons Attribution-Noncommercial 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 4.0 License.

Rights Information

@2022 Kye W Shi


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.