Strong nondeterministic Turing reduction - a technique for proving intractability (Q1262762)

Several problems connected with sorting networks are proved to be NP- complete. The main result of the paper under review is that properties of sorting networks requiring test sets of size at least \(c2^ n\) (c fixed, n is the number of inputs of the network) define problems which are complete in NP with respect to the strong polynomial time Turing reducibility studied by \textit{T. J. Long} [Theor. Comput. Sci. 21, 1-25 (1982; Zbl 0521.03028)]. This reducibility is the Turing counterpart of the strong polynomial time many-one reducibility (\(\gamma\)-reducibility) introduced by \textit{L. Adleman} and \textit{K. Manders} [Reductions that lie, 20th Foundations of Computer Science, 397-410 (1977)]. Adleman and Manders had exhibited natural problems which are \(\gamma\)-complete in NP, but it was not known whether there exist natural problems complete with respect to the strong polynomial time Turing reducibility.