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.