US-Japan Cooperative Science: Complexity Theory for Strategic Goals

美日合作科学：战略目标的复杂性理论

• 批准号: 9726724
• 负责人: Kenneth Regan
• 金额: $ 3.1万
• 依托单位: SUNY at Buffalo
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-04-01 至 2002-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9726724&HistoricalAwards=false
• 关键词: US; Japan; Cooperative; Science; Complexity

9726724 Regan This award supports a three year collaborative research project between Professor Kenneth Regan of SUNY, Buffalo and Professor Osamu Watanabe of the Tokyo Institute of Technology in Japan. The researchers will undertake a study of complexity theory for strategic goals. The main objective is the development of more refined tools for analyzing the complexity of computations than are currently most commonly employed in the field. Particular areas to be investigated include: (1) linear and quasi-linear time reductions between problems, (2) low-level circuit-based classes and reductions, often with quasi-linear bounds on circuit size, (3) average-case complexity, including a determination of which of several competing polynomial-time formalisms is best suited for lower time bound analysis, and (4) a new theory of one- way functions that realize certain concrete polynomial complexity gaps, such as being quasilinear-time computable but not inevitable in less than quadratic time. This project brings together the efforts of scientists, in both countries, that have complementary expertise and research capabilities. The development of a more acute analysis of computational costs should help gauge its practical effectiveness now, and its strategic potential as a guide for future investigations. Extending theories of (quasi-)linear time and of low-level classes and reductions should provide a precise understanding of what facets of problems make them hard to solve and how these facets are related between problems. It is further expected that it will be possible to understand the relationship between average-case complexity and the nature-and-distribution of such hard instances. Through the exchange of ideas and technology, this project will broaden our base of basic knowledge and promote international understanding and cooperation. ***

小行星9726724 该奖项支持纽约州立大学布法罗分校的Kenneth Regan教授和日本东京工业大学的Osamu Watanabe教授之间为期三年的合作研究项目。 研究人员将对战略目标的复杂性理论进行研究。 其主要目标是开发出比目前该领域最常用的更精细的工具来分析计算的复杂性。 需要调查的具体领域包括：（1）问题之间的线性和准线性时间约简，（2）基于电路的低级类和约简，通常具有电路大小的准线性边界，（3）平均情况复杂度，包括确定几个竞争的多项式时间形式主义中的哪一个最适合于较低的时间边界分析，以及（4）单向函数的新理论，其实现了某些具体的多项式复杂性缺口，例如是准线性时间可计算的，但在小于二次时间内不是不可避免的。 该项目汇集了两国科学家的努力，他们具有互补的专业知识和研究能力。对计算成本进行更精确的分析，应该有助于衡量其现在的实际有效性，以及其作为未来研究指南的战略潜力。 扩展（准）线性时间理论和低层次类和归约理论应该提供一个精确的理解，即问题的哪些方面使它们难以解决，以及这些方面在问题之间是如何联系的。 我们还希望能够理解平均情况复杂度与这种困难实例的性质和分布之间的关系。 通过交流思想和技术，该项目将扩大我们的基础知识，促进国际理解与合作。 ***