RUI: Structural Aspects of Average-Case NP-Completeness

RUI：平均情况 NP 完备性的结构方面

• 批准号: 9424164
• 负责人: Jie Wang
• 金额: $ 7.49万
• 依托单位: University of North Carolina Greensboro
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-06-01 至 1999-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9424164&HistoricalAwards=false
• 关键词: RUI; Structural; Aspects; Average; Case

This RUI project is a companion project to the RUI project CCR-9503601 (PI: Belanger) of Northeast Missouri State University. (1) The first part of this research project aims to better understand the properties and structures of average-case NP-complete problems under randomizing reductions. Randomizing reducibility is a powerful tool used to learn about average-case completeness. In particular, the existence of isomorphisms between complete problems and the structure of complete problems under randomizing reductions are studied. Polynomial isomorphisms are explored in the setting of randomizing many-to-one reductions based on recent results on the NP-isomorphism problem with respect to random instances, which have explicit support for this goal. (2) The second research topic is rankable distributions. P-rankable distributions were proposed recently to capture the ranking of probability distributions, but they are not directly comparable to p-time computable distributions used in the literature. The goal here is to investigate whether p-rankable distributions can provide harder instances than p-time computable distributions for randomized NP decision problems and randomized NP search problems.

本RUI项目是东北密苏里州立大学RUI项目CCR-9503601 （PI: Belanger）的伙伴项目。(1)本研究项目的第一部分旨在更好地理解随机化约简下平均情况np完全问题的性质和结构。随机化可约性是学习平均情况完备性的有力工具。特别地，研究了随机化约下完全问题的结构与完全问题之间同构的存在性。基于最近关于随机实例的np同构问题的结果，在随机化多对一约简的背景下探讨了多项式同构，这些结果明确支持这一目标。(2)第二个研究课题是排名分布。最近提出了p- rank分布来捕捉概率分布的排名，但它们不能直接与文献中使用的p-时间可计算分布进行比较。这里的目标是研究对于随机NP决策问题和随机NP搜索问题，p-可排名分布是否能提供比p-时间可计算分布更难的实例。