Some Remarks on Witness Functions for Nonpolynomial and Noncomplete Sets in NP
Some Remarks on Witness Functions for Nonpolynomial and Noncomplete Sets in NP
复制标题
关于NP中非多项式和非完备集见证函数的一些评论
DOI：
10.1016/0304-3975(85)90140-9
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
Paul Young
中科院分区：
文献类型：
--
作者：
D. Joseph;Paul Young
本文给出了NP和coNP中集合的证明函数的两个结果。第一，任何一个集合如果有一个多项式可计算的函数证明它不属于coNP，那么它至少是NP难的。从这个结果可以得出，NP-coNP中的任何集合，如果有一个多项式可计算的函数证明了这个事实，那么它对于NP来说一定是完备的。其次，如果B是任何一个集合，对于它有一个多项式可计算函数，通过证明NP中的某个固定集合不在PB中，证明它对NP是不完备的，那么B一定已经在NP中了。因此，对于NP-coNP中的两个集合，没有多项式可计算的函数证明一个不能多项式约简到另一个。在证明第一个结果时，我们引入了ak-创造集的概念，并证明了所有k-创造集都是NP-完全的。由于这些集似乎不是所有的多项式同构，我们反对的猜想伯曼和哈特曼是所有的NP-完全集是同构的SAT与我们自己的猜想thatnot所有的k-创造集是同构的SAT。我们给出的证明是递归理论的风格，但直接。
We present two results about witness functions for sets in NP and coNP. First, any set that has a polynomially computable function which witnesses that it is not in coNP must be at least NP-hard. It follows from this result that any set in NP-coNP that has a polynomially computable function which witnesses this fact must already be complete for NP. Second, ifBis any set for which there is a polynomially computable function which witnesses that it is not complete for NP by witnessing that some fixed set in NP is not in PB, thenBmust already be in NP ⊃ coNP. Thus, for two sets in NP-coNP there are no polynomially computable functions which witness that one is not polynomially reducible to the other. In proving the first result we introduce the notion of ak-creative set and prove that allk-creative sets are NP-complete. Since these sets seem not to be all polynomially isomorphic, we counter the conjecture of Berman and Hartmanis that all NP-complete sets are isomorphic to SAT with our own conjecture thatnot all k-creative sets are isomorphic to SAT. The proofs we give are recursion-theoretic in style, but straightforward.