Query-monotonic Turing reductions

DOI10.1016/J.TCS.2007.04.014MaRDI QIDQ2383592zbMATH OpenOpenAlexFDO

Authors Mayur Thakur, Lane A. Hemaspaandra

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

zbMATH Keywords

NP-completenessquery-decreasing Turing reductionquery-increasing Turing reductionquery-monotonic Turing reductionquery-nondecreasing Turing reductionquery-nonincreasing Turing reductiontight paddable set

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Computing and Combinatorics
• Monotonic reductions, representative equivalence, and compilation of intractable problems
• Reductions for Monotone Boolean Circuits
• Reductions for monotone Boolean circuits
• Turing reducibility in the fine hierarchy
• The monoidal structure of Turing machines
• scientific article; zbMATH DE number 1424044
• Computer Science Logic
• Comparing the succinctness of monadic query languages over finite trees
• About Segment Complexity of Turing Reductions

Cites work

• A comparison of polynomial time completeness notions
• A comparison of polynomial time reducibilities
• Computing and Combinatorics
• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 48150 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 512802 (Why is no real title available?)
• scientific article; zbMATH DE number 1072532 (Why is no real title available?)
• scientific article; zbMATH DE number 1091107 (Why is no real title available?)
• scientific article; zbMATH DE number 1543293 (Why is no real title available?)
• Immunity and Simplicity for Exact Counting and Other Counting Classes
• Immunity, Relativizations, and Nondeterminism
• Mathematical Foundations of Computer Science 2005
• On helping by robust oracle machines
• On Isomorphisms and Density of NP and Other Complete Sets
• On log-tape isomorphisms of complete sets
• ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
• One-way permutations and self-witnessing languages
• P-immune sets with holes lack self-reducibility properties.
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• P-selectivity: Intersections and indices
• Query Order
• Reductions among polynomial isomorphism types
• Robust algorithms: a different approach to oracles
• Robust reductions
• Separating NP-completeness notions under strong hypotheses
• Separation of NP-completeness notions
• The polynomial-time hierarchy
• The space complexity of approximating the frequency moments
• The structure of the honest polynomial m-degrees
• Threshold Computation and Cryptographic Security

Cited in

(2)

• Quasi-injective reductions
• Computing and Combinatorics

This page was built for publication: Query-monotonic Turing reductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2383592)