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教授，计算机科学与信息数学系，Electro-Communices，Electro-Communications of Electro-Communications of Electro-Communications of Electro-Communications of Electro-Communications of Electro-Comparications，dokeko ofkyo。 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从研究完美哈希功能的研究中提出的问题。