Reductions to Sets of Low Information Content
Reductions to Sets of Low Information Content
复制标题
减少低信息内容集
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
T. Thierauf
中科院分区：
文献类型：
--
作者：
V. Arvind;Yenjo Han;L. Hemaspaandra;J. Köbler;A. Lozano;M. Mundhenk;Mitsunori Ogihara;U. Schöning;R. Silvestri;T. Thierauf
本文研究了关于稀疏集的三个基本问题：(1)NP在什么类型的约简下可能有硬或完全稀疏集？(2)如果集合a约简为一个稀疏集，是否就可以得出a可约为某个相对于a“简单”的稀疏集？(3)关于NP可能具有低实例复杂度的硬集或完全集的哪些类型的约简，以及与之相关的低实例复杂度集合类的结构是什么？．pp关于第一个和第三个问题，直观地，人们会期望，即使对于柔性约简NP也不太可能有信息含量低的完备集。关于第二个问题，人们可能会直观地感觉到，通过将一个集合约简为一个稀疏集这一事实强加给它的结构使得我们确实可以找到一个可以伪装成原始稀疏集的简单稀疏集。这两种直觉在很多方面都得到了当前文献和本文结果的证实。
This paper is concerned with three basic questions about sparse sets: (1) With respect to what types of reductions might NP have hard or complete sparse sets? (2) If a set A reduces to a sparse set, does it follow that A is reducible to some sparse set that is "simple" relative to A? (3) With respect to what types of reductions might NP have hard or complete sets of low instance complexity, and, relatedly, what is the structure of the class of sets with low instance complexity? .pp With respect to the first and third questions, intuitively one would expect that even with respect to flexible reductions NP is unlikely to have complete sets whose information content is low. With respect to the second question, one might intuitively feel that the structure imposed on a set by the fact that it reduces to a sparse set makes it plausible that we can indeed find a simple sparse set that can masquerade as the original sparse set. These two intuitions are in many ways certified by the current literature, and by the results of this paper.