Complexity of Feasible Computations
Complexity of Feasible Computations
批准号:
9002292
负责人:
Alan Selman
金额:
$19.98万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
1990
资助国家:
美国
项目状态:
已结题
起止时间:
1990-09-01 至 1994-02-28
中文摘要
研究了可行解的计算复杂度 计算。 该项目有两个目标: 为公钥建立了坚实复杂性理论基础 密码学;揭示个体复杂性 类,如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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Complexity of Feasible Computations
-
批准号:0307077
-
项目类别:Continuing Grant
-
资助金额:$14.98万
-
财政年份:2003
-
负责人:Alan Selman
-
依托单位:
Workshop on Reserach in Theoretical Computer Science
-
批准号:9906118
-
项目类别:Standard Grant
-
资助金额:$2.59万
-
财政年份:1999
-
负责人:Alan Selman
-
依托单位:
Complexity of Feasible Computations
-
批准号:9400229
-
项目类别:Continuing Grant
-
资助金额:$36.08万
-
财政年份:1994
-
负责人:Alan Selman
-
依托单位:
Complexity of Feasible Computations (Computer Research)
-
批准号:8696082
-
项目类别:Continuing grant
-
资助金额:$0.0万
-
财政年份:1986
-
负责人:Alan Selman
-
依托单位:
Structure in Complexity Theory Conference to be held on May 26-29, 1986, in Berkeley, California
-
批准号:8512929
-
项目类别:Standard Grant
-
资助金额:$1.5万
-
财政年份:1985
-
负责人:Alan Selman
-
依托单位:
Complexity of Feasible Computations (Computer Research)
-
批准号:8402033
-
项目类别:Continuing Grant
-
资助金额:$9.26万
-
财政年份:1984
-
负责人:Alan Selman
-
依托单位:
Complexity of Feasible Computations (Computer Research)
-
批准号:8120263
-
项目类别:Standard Grant
-
资助金额:$4.0万
-
财政年份:1982
-
负责人:Alan Selman
-
依托单位:
Studies in Nondeterminism and Relative Computability
-
批准号:7506340
-
项目类别:Standard Grant
-
资助金额:$6.47万
-
财政年份:1975
-
负责人:Alan Selman
-
依托单位:
海外基金