RUI: Structural Aspects of Average-Case NP-Completeness

点击翻译按钮获取中文摘要

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.