Complexity of Feasible Computations
Complexity of Feasible Computations
批准号:
9400229
负责人:
Alan Selman
金额:
$36.08万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
1994
资助国家:
美国
项目状态:
已结题
起止时间:
1994-09-15 至 1998-08-31
中文摘要
9400229 Selman这项工作将继续对可行计算的计算复杂性进行研究。 我们的目标是区分属性的复杂性类,包含可行的计算,从那些不,以揭示丰富的结构,个别复杂性类,如NP,似乎有,并增加了解低层次的复杂性类之间的结构关系。 重点将是继续研究多值计算的复杂性以及非均匀复杂性和均匀复杂性之间的关系。 该方法是结构复杂性的标准范式,即,引出复杂性类的结构属性,而不是分析单个具体问题。 ***
英文摘要
9400229 Selman This work will continue the research effort on the computational complexity of feasible computations. The objective is to distinguish properties of complexity classes that contain feasible computations from those that do not, 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. The emphasis will be to continue research on the complexity of multivalued computations and on relations between nonuniform and uniform complexity. The approach is the standard paradigm of structural complexity, that is, to elicit structural properties of complexity classes rather than analyze 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
-
批准号:9002292
-
项目类别:Continuing Grant
-
资助金额:$19.98万
-
财政年份:1990
-
负责人: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
-
依托单位:
海外基金