Complexity of Feasible Computations

研究了可行计算的计算复杂度问题。该项目的目标有两个：为公钥密码学建立一个坚实的复杂性理论基础；揭示单个复杂性类（如NP）似乎具有的丰富结构，并增加对低级别复杂性类之间结构关系的理解。重点之一是继续研究为密码学奠定基础的结构复杂性理论。该方法是直接基于复杂性类的结构性质来研究密码假设（或原语）的存在性，而不是基于单个具体问题的假定难解性。

The reseach concerns the computational complexity of feasible computations. The objectives of this project are twofold: to establish a firm complexity theoretic underpinning for public-key cryptography; to reveal the rich structure that individual complexity classes, such as NP, appear to have, and to increase understanding of the structural relations between low-level complexity classes. One emphasis will be to continue research in structural complexity theory that lays a foundation for cryptography. The approach is to base the investigation of existence of cryptographic assumptions (or primitives) directly on structural properties of complexity classes, rather than on presumed intractability of individual concrete problems.