US-Japan Cooperative Science: Complexity Theory for Strategic Goals

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

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. ***