The Structure of Complete Sets and Polynomial Reducibilities
完备集的结构和多项式可约性
基本信息
- 批准号:9103055
- 负责人:
- 金额:--
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:1991
- 资助国家:美国
- 起止时间:1991-09-01 至 1995-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This research attempts to gain a better understanding of the intrinsic properties of complete sets for many natural complexity classes. The research will explore how the complexity-theoretic properties of complete sets are affected by the strength of the reducibilities defining them, and the relationships between these properties and the central problems in complexity theory. One such property is immunity, which examines whether all complete problems have larger subproblems which are easier to solve than the full problem. This research bears upon the existence of certain types of approximations to these intractable sets. Another area of study is the strength of efficient reductions between pairs of complete sets and the possibility of reductions from complete sets to sparse sets or other sets with a particular structure. The relationships between the complexity-theoretic results in these areas and other current research problems such as the isomorphism problem and the existence of certain types of one-way functions are a central focus of this work.
本研究试图更好地理解许多自然复杂性类的完备集的内在性质。该研究将探讨如何完整的集合的复杂性理论的属性是由定义它们的可约性的强度,以及这些属性和复杂性理论的中心问题之间的关系的影响。一个这样的属性是免疫,它检查是否所有完整的问题都有更大的子问题,这些子问题比完整的问题更容易解决。这项研究关系到这些棘手的集合的某些类型的近似的存在。另一个研究领域是完整集合对之间有效约简的强度,以及从完整集合约简到稀疏集合或具有特定结构的其他集合的可能性。在这些领域的复杂性理论的结果和其他当前的研究问题,如同构问题和某些类型的单向函数的存在之间的关系是这项工作的中心焦点。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Steven Homer其他文献
Non-Uniform Reductions
- DOI:
10.1007/s00224-008-9163-5 - 发表时间:
2009-01-09 - 期刊:
- 影响因子:0.400
- 作者:
Harry Buhrman;Benjamin Hescott;Steven Homer;Leen Torenvliet - 通讯作者:
Leen Torenvliet
A Short History of Computational Complexity
计算复杂性简史
- DOI:
- 发表时间:
2002 - 期刊:
- 影响因子:0
- 作者:
L. Fortnow;Steven Homer - 通讯作者:
Steven Homer
Minimal pairs and complete problems
- DOI:
10.1016/0304-3975(94)90234-8 - 发表时间:
1994-09-26 - 期刊:
- 影响因子:
- 作者:
Klaus Ambos-Spies;Steven Homer;Robert I. Soare - 通讯作者:
Robert I. Soare
Absolute results concerning one-way functions and their applications
- DOI:
10.1007/bf02088290 - 发表时间:
1989-12-01 - 期刊:
- 影响因子:0.400
- 作者:
Steven Homer;Jie Wang - 通讯作者:
Jie Wang
Completeness for nondeterministic complexity classes
- DOI:
10.1007/bf02090397 - 发表时间:
1991-12-01 - 期刊:
- 影响因子:0.400
- 作者:
Harry Buhrman;Steven Homer;Leen Torenvliet - 通讯作者:
Leen Torenvliet
Steven Homer的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Steven Homer', 18)}}的其他基金
XPS: FULL: CCA: Collaborative Research: Automatically Scalable Computation
XPS:完整:CCA:协作研究:自动可扩展计算
- 批准号:
1533663 - 财政年份:2015
- 资助金额:
-- - 项目类别:
Standard Grant
Quantum Computation and Complexity Theory
量子计算和复杂性理论
- 批准号:
9988310 - 财政年份:2000
- 资助金额:
-- - 项目类别:
Continuing grant
U.S.-Netherlands Cooperative Research in Complexity Theory (Computer Science)
美国-荷兰复杂性理论合作研究(计算机科学)
- 批准号:
9123551 - 财政年份:1992
- 资助金额:
-- - 项目类别:
Standard Grant
Parallel Automated Reasoning and Clause-Graph Analysis
并行自动推理和子句图分析
- 批准号:
9003030 - 财政年份:1990
- 资助金额:
-- - 项目类别:
Standard Grant
The Structure of Complete Sets And Honest Polynomial Reducibilities
完备集结构与诚实多项式可约性
- 批准号:
8814339 - 财政年份:1989
- 资助金额:
-- - 项目类别:
Standard Grant
Applications of Non-Linear Systems to Coding and Communications
非线性系统在编码和通信中的应用
- 批准号:
8608137 - 财政年份:1987
- 资助金额:
-- - 项目类别:
Standard Grant
Non-Linear Recurrence Relations, Quadratic Automata and Applications (Computer Research)
非线性递推关系、二次自动机及其应用(计算机研究)
- 批准号:
8202942 - 财政年份:1982
- 资助金额:
-- - 项目类别:
Standard Grant
Non-Linear Recurrence Relations, Quadratic Automata and Applications (Computer Research)
非线性递推关系、二次自动机及其应用(计算机研究)
- 批准号:
8218383 - 财政年份:1982
- 资助金额:
-- - 项目类别:
Standard Grant
相似海外基金
Toward a more complete understanding of coastal upwelling dynamics
更全面地了解沿海上升流动力学
- 批准号:
2343008 - 财政年份:2024
- 资助金额:
-- - 项目类别:
Standard Grant
DryBrain: single cell-resolution molecular mechanisms ensuring tolerance of insect nervous system to complete desiccation
DryBrain:单细胞分辨率分子机制确保昆虫神经系统对完全干燥的耐受性
- 批准号:
23K26919 - 财政年份:2024
- 资助金额:
-- - 项目类别:
Grant-in-Aid for Scientific Research (B)
RII Track-4:NSF: Direct and Complete Characterization of Electronic Properties of Materials Under Pressure
RII Track-4:NSF:压力下材料电子特性的直接完整表征
- 批准号:
2327363 - 财政年份:2024
- 资助金额:
-- - 项目类别:
Standard Grant
A complete double copy dictionary and its applications
完整的双副本词典及其应用
- 批准号:
2868821 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Studentship
Towards a complete characterization of the metastasis founder clones in colorectal cancer
全面表征结直肠癌转移起始克隆
- 批准号:
10973772 - 财政年份:2023
- 资助金额:
-- - 项目类别:
STTR Phase II: Stem Cell Delivery in Microscopic Hydrogel Droplets for Faster and More Complete Healing of Equine Tendon and Ligament Injuries
STTR 第二阶段:以微小水凝胶液滴形式输送干细胞,以更快、更完全地治愈马肌腱和韧带损伤
- 批准号:
2304324 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Cooperative Agreement
Complete inhibition of ROCK signaling in diabetic nephropathy
完全抑制糖尿病肾病中的 ROCK 信号传导
- 批准号:
23K07709 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Grant-in-Aid for Scientific Research (C)
Development of multi omics data analysis method using short/long read integration and complete human reference sequences
使用短/长读长集成和完整的人类参考序列开发多组学数据分析方法
- 批准号:
23K11300 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Grant-in-Aid for Scientific Research (C)
Delta-Complete SMT Solvers for Learning and Optimization Algorithms
用于学习和优化算法的 Delta-Complete SMT 求解器
- 批准号:
2869702 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Studentship
Challenges to the problem of elder-to-elder nursing care from a proposal for a complete unrestrained monitoring method of wheelchair operating mechanisms
轮椅操作机构完整无限制监测方法的提出对长者护理问题的挑战
- 批准号:
23K01928 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Grant-in-Aid for Scientific Research (C)