- Providing an Alternate Version of the Logspace Hierarchy to Recreate the Polynomial Hierarchy
- Project Year:
2017
- REU Student (s):
Marina Knittel | Harvey Mudd College
- Student 1 Institution:
Harvey Mudd College
- Project Mentor:
Eric Allender
- Project Mentor Area:
Computer Science
- Project Abstract:
The polynomial hierarchy is a central topic in computer science today, particularly because of its close relationship with the infamous question of whether or not P=NP. For instance, we know that P=NP implies that the polynomial hierarchy collapses. Therefore studying the polynomial hierarchy, for instance finding new ways to define its structure, is an important part of research in theoretical computer science. This project aimed to discover a new hierarchical structure that has a strong correspondence with the polynomial hierarchy. In the end, we discovered a structure based off of the logspace hierarchy that is equivalent to the polynomial hierarchy when given an additional quantifier. The main consequence of this result is that we now have a new way to consider the polynomial hierarchy. Additionally, we were able to define a new set of complete problems for various levels of the hierarchy. More generally, we hope this work can act as a stepping stone for further study in formulations of complexity classes that have somehow relate to the polynomial hierarchy. The results also provide a strong framework for the discovery of new natural complete problems for the polynomial hierarchy phrased in terms of the properties of our model as opposed to the standard model. The ultimate goal is to generally improve our understanding of the various components of the polynomial hierarchy, especially P and NP, in the hopes of answering broader questions such as whether or not P=NP.
