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.
