U.S.-Japan Cooperative Research: Counting Classes, Closure Properties, and Hash Functions

该奖项将支持罗彻斯特大学计算机科学系Lane Hemachandra教授和东京工业大学计算机科学系Osamu Watanabe教授之间为期两年的美日合作研究项目。参与该项目的其他研究人员包括康奈尔大学计算机科学系Juris Hartmanis教授、东京工业大学信息科学系Kojiro Kobayashi教授、东京电子通信大学计算机科学与信息数学系Mitsunori Ogiwara教授和Seinosuke Toda教授。日本。该项目主要关注一些自然的中等复杂性类的闭包性质，如：(1)关键函数类的看似“中间”闭包性质的相对复杂性——这些性质似乎既不为类所拥有，也不为类所难以拥有，以及(2)是否所有无限NP集都有（相对）简单的无限稀疏子集的问题，这个问题源于对完美哈希函数的研究。

This award will support a two-year U.S.-Japan cooperative research project between Professor Lane Hemachandra, Department of Computer Science, University of Rochester, and Professor Osamu Watanabe, Department of Computer Science, Tokyo Institute of Technology. Other investigators involved in the project are Professor Juris Hartmanis, Department of Computer Science, Cornell University, Professor Kojiro Kobayashi, Department of Information Sciences, Tokyo Institute of Technology, and Professors Mitsunori Ogiwara and Seinosuke Toda, both of the Department of Computer Science and Information Mathematics, University of Electro-Communications, Tokyo, Japan. The project is focused on closure properties of some natural intermediate complexity classes such as The investigators will focus on two areas in complexity theory: (1) the realtive complexity of seemingly "intermediate" closure properties of key function classes--properties that seem neither to be possessed by the classes nor to be hard for the classes, and (2) the question of whether all infinite NP sets have infinite sparse subsets that are (relatively) siimple, a question that springs from the study of perfect hash functions.