Strong nondeterministic Turing reduction - a technique for proving intractability (Q1262762): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:38, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Strong nondeterministic Turing reduction - a technique for proving intractability |
scientific article |
Statements
Strong nondeterministic Turing reduction - a technique for proving intractability (English)
0 references
1989
0 references
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.
0 references
strong nondeterministic Turing reduction
0 references
NP-completeness
0 references
sorting networks
0 references