Strong nondeterministic Turing reduction - a technique for proving intractability

DOI10.1016/0022-0000(89)90017-2zbMath0686.68032OpenAlexW2068873365MaRDI QIDQ1262762

Moon Jung Chung, Bala Ravikumar

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90017-2

zbMATH Keywords

NP-completenesssorting networksstrong nondeterministic Turing reduction

Mathematics Subject Classification ID

Related Items (2)

Comparing reductions to NP-complete sets ⋮ Single-exception sorting networks and the computational complexity of optimal sorting network verification

Cites Work

• Bounds on the size of test sets for sorting and related networks
• Strong nondeterministic polynomial-time reducibilities
• A comparison of polynomial time reducibilities
• Polynomial Time Enumeration Reducibility
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Strong nondeterministic Turing reduction - a technique for proving intractability