RIA: Isomorphism Problems in Structural Complexity Theory

本课题主要研究复杂类中完备集的同构问题。例如，结构复杂性理论中最重要的公开问题之一就是在多项式时间可计算和多项式时间可逆双射下，NP-完备集是否都同构。本文主要研究自然复杂类中的完全问题存在或不存在这种同构的条件，如NP和指数时间，以及这些条件的含义。除了多项式时间同构，多项式时间等价性的弱形式也被研究用于完全问题。

This project is concerned with isomorphism problems for complete sets in complexity classes. For example, one of the most important open questions in structural complexity theory is whether the NP-complete sets are all isomorphic under polynomial time computable and polynomial time invertible bijections. The study focuses on conditions under which such isomorphisms do or do not exist for complete problems in natural complexity classes, such NP and exponential time, and on the implications of these conditions. In addition to polynomial time isomorphism, weaker forms of polynomial time equivalence are also being investigated for complete problems.