Strong nondeterministic Turing reduction--a Technique for Proving Intractability
Moon Jung Chung, Bala Ravikumar · 1987
Selman and Long introduced the concept of a strong nondeterministic reduction (denoted by ≥tin) as a generalization of Adleman-Manders' γ-reduction. This reduction has the property that if A ≤tinB, then A ∈ NPB⋒ co-NPB. Thus if Β is a problem in NP such that A ≤tinfor all A ∈ NP, then Β is not Ρ unless NP = co-NP, providing a strong evidence for the intractability of B. We say in this case that A is ≤tin-complete for NP. Our main result is the proof of ≤tin-completeness for NP of a combinatorial problem arising in the analysis of sorting-type networks. This is the first example (to the best of authors' knowledge) of a non number-theoretic problem which is shown to be intractable using a nondeterministic reduction. It is not known if this problem is NP-complete. Earlier, Adleman and Manders used nondeterministic reductions to show the intractability of some number-theoretic problems. Our problem can be stated as follows. ‘Given a network, does it possess a given property?’, e.g., ‘is it a sorting network?’. We show that testing of any property that has an exponentially large test set is ≤tin-complete for NP. On our way to the main result, we also show the NP-completeness or coNP-completeness of some fundamental network testing problems.