Strong nondeterministic Turing reduction - a technique for proving intractability (Q1262762): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Bala Ravikumar / rank | |||
Property / author | |||
Property / author: Bala Ravikumar / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0022-0000(89)90017-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2068873365 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bounds on the size of test sets for sorting and related networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of theorem-proving procedures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4142699 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4057549 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A comparison of polynomial time reducibilities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3946078 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Strong nondeterministic polynomial-time reducibilities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Polynomial Time Enumeration Reducibility / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:41, 20 June 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