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.