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

该奖项将支持为期两年的美国-日本合作社 莱恩·赫马钱德拉教授，系 罗切斯特大学计算机科学系教授 Osamu Watanabe，计算机科学系，东京 理工学院 参与该项目的其他调查人员 是Juris Hartmanis教授，计算机科学系， 康奈尔大学教授小林次郎， 东京工业大学信息科学系， 教授Mitsunori Ogiwara和Seinosuke户田，都是 计算机科学与信息数学系， 电子通信大学，日本东京。 该项目的重点是封闭性质的一些自然 中间复杂性类，例如 研究人员将集中在复杂性理论的两个领域：（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.