Some remarks on witness functions for nonpolynomial and noncomplete sets in NP

AbstractWe 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, if B is 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, then B must 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 a k-creative set and prove that all k-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 that not all k-creative sets are isomorphic to SAT. The proofs we give are recursion-theoretic in style, but straightforward