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
Zoom (see link in Abstract)

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 . Work of Richard Ladner that shows the existence of NP intermediate classes of problems given will be discussed.

The graph isomorphism problem, a commonly believed member of the intermediate class, and the subgraph isomorphism problem will be discussed, primarily based on a type of algorithm for them. Finally, a brief discussion of polynomial hierarchy will be introduced, based on the discussion of these isomorphism problems.

Zoom link

Event contact: jonathan dot pakianathan at rochester dot edu