Query-monotonic Turing reductions
DOI10.1016/j.tcs.2007.04.014zbMath1123.68042OpenAlexW2013235410MaRDI QIDQ2383592
Mayur Thakur, Hemaspaandra, Lane A.
Publication date: 19 September 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1802/521
NP-completenessquery-decreasing Turing reductionquery-increasing Turing reductionquery-monotonic Turing reductionquery-nondecreasing Turing reductionquery-nonincreasing Turing reductiontight paddable set
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- P-selectivity: Intersections and indices
- Robust algorithms: a different approach to oracles
- Reductions among polynomial isomorphism types
- A comparison of polynomial time completeness notions
- On helping by robust oracle machines
- Robust reductions
- A comparison of polynomial time reducibilities
- The polynomial-time hierarchy
- On log-tape isomorphisms of complete sets
- The space complexity of approximating the frequency moments
- The structure of the honest polynomial m-degrees
- P-immune sets with holes lack self-reducibility properties.
- One-way permutations and self-witnessing languages
- Separation of NP-Completeness Notions
- Immunity, Relativizations, and Nondeterminism
- ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Query Order
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- Threshold Computation and Cryptographic Security
- Mathematical Foundations of Computer Science 2005
- Computing and Combinatorics
- Separating NP-completeness notions under strong hypotheses
This page was built for publication: Query-monotonic Turing reductions
