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

美日合作研究：类计数、闭包性质和哈希函数

• 批准号: 9116781
• 负责人: Lane Hemaspaandra
• 金额: $ 2.07万
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-09-01 至 1995-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9116781&HistoricalAwards=false
• 关键词: U.S.; Japan; Cooperative; Research; Counting

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.

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