RIA: Isomorphism Problems in Structural Complexity Theory

点击翻译按钮获取中文摘要

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.