Strong nondeterministic turing reduction—A technique for proving intractability

摘要

Since the pioneering work of Cook and Karp, an extensive effort has been made in identifying hundreds of apparently intractable (i.e., NP-complete) problems. At the same time, attempts were also made to discover new methods to establish computational intractability. Notably, Adleman and Manders showed some number-theoretic problems to be intractable basing their intractability claim on the (stronger) assumption NP ≠ co-NP rather than the usual assumption P ≠ NP. The key idea behind the extension proposed by Adleman and Manders was to use a more general type of reduction (called γ-reduction) in the problem transformation. Specifically, the reduction was allowed to be nondeterministic. Timothy Long attempted to study the nature of γ-reduction and its natural extension called ⩽tsn-reduction from a structure-theoretic point of view. It was open whether the latter reduction was really a practical tool, i.e., whether it can be used to prove the intractability of “natural” problems, particularly problems of combinatorial type. In this paper we answer this question in the affirmative. Our work was, of course, motivated by a problem in concrete complexity that we wanted to analyze. It arises from the testing of comparator networks of which a sorting network is a well-known example. Suppose we want to test if a given comparator network is a sorting network. This problem turns out to be coNP-complete. Also “sortedness” is a hard property to test based on input-output behavior in the sense that one has to test an exponential number of strings to decide if a network is a sorting network. Our main result is a generalization of this correlation between intractability and the size of the number of input-output tests: “The problem of testing if a network has a given ‘property’ whose testing requires an exponentially large number of input-output tests is (apparently) intractable, i.e., it is not in P unless NP = co-NP. ” On our way to the main result, we also show the NP-completeness or the coNP-completeness of some fundamental network testing problems.