Honors Oral Exam

On NP-intermediate isomorphism problems and Polynomial Hierarchy

Xin Lu (University of Rochester)

Friday, May 1st, 2020
2:00 PM - 3:00 PM
Since being introduced, the concept of P and NP complexity classes of algorithms have been the main focus in complexity theory. Despite decades of efforts, it remains an open problem whether P = NP. However, most professionals hold the belief that the two classes differ. In this paper, discussion of these two categories of problems will occur, assuming $P \neq NP$. Work of Richard Ladner that shows the existence of NP intermediate classes of problems given $P \neq NP$ will be discussed.