期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A , B , C , and D be nonempty sets belonging to NP. A {\em smart} reduction between the disjoint NP-pairs ( A B ) and ( C D ) is a Turing reduction with the additional property that if the input belongs to A B , then all queries belong to C D . We prove under the reasonable assumption UP co - UP has a P-bi-immune set that there exist disjoint NP-pairs ( A B ) and ( C D ) such that ( A B ) is truth-table reducible to ( C D ) , but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DisjNP has a truth-table-complete disjoint NP-pair, but has no many-one-complete disjoint NP-pair.
B ) and ( C 
