Probabilistic autoreductions

DOI10.1007/978-3-662-49192-8_34MaRDI QIDQ2794381zbMATH OpenOpenAlexFDO

Authors Liyu Zhang, Chen Yuan, Haibin Kan

Publication date 10 March 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-49192-8_34

zbMATH Keywords

complete setscomputational complexityprobabilistic many-one reductionsprobabilistic polynomial-time autoreductionstruth-table reductions

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Autoreducibility of NP-complete sets
• Autoreducibility of NP-complete sets under strong hypotheses
• Autoreducibility, mitoticity, and immunity
• Autoreducibility of complete sets for log-space and polynomial-time reductions
• Mathematical Foundations of Computer Science 2005

Cited in

(10)

• On being incoherent without being very hard
• Randomness and completeness in computational complexity
• Autoreducibility of NP-complete sets under strong hypotheses
• Random-Self-Reducibility of Complete Sets
• Infinitely‐Often Autoreducible Sets
• Autoreducibility of NP-complete sets
• Automatic Generation of Optimal Reductions of Distributions
• Algorithms and Computation
• Toward automating the discovery of decreasing measures
• On the autoreducibility of functions

This page was built for publication: Probabilistic autoreductions

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