US-Japan Cooperative Science: Complexity Theory for Strategic Goals

点击翻译按钮获取中文摘要

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