On the autoreducibility of functions
From MaRDI portal
Publication:970103
DOI10.1007/s00224-008-9127-9zbMath1209.68262MaRDI QIDQ970103
Ogihara, Mitsunori, Piotr Faliszewski
Publication date: 10 May 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1802/4042
reductions; function classes; autoreducibility; complete functions; length-decreasing self-reducibility
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- The complexity of combinatorial problems with succinct input representation
- The complexity of optimization problems
- On counting and approximation
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- On being incoherent without being very hard
- On the closure of certain function classes under integer division by polynomially-bounded functions
- A comparison of polynomial time reducibilities
- On hiding information from an oracle
- Gap-definable counting classes
- The power of adaptiveness and additional queries in random-self- reductions
- \(p\)-selective self-reducible sets: a new characterization of P
- Closure properties and witness reduction
- A complexity theory for feasible closure properties
- Self-reducibility
- Random-Self-Reducibility of Complete Sets
- #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
- Relativization of questions about log space computability
- Computational Complexity of Probabilistic Turing Machines
- Complexity classes defined by counting quantifiers
- Mitotic recursively enumerable sets
- Separating Complexity Classes Using Autoreducibility
- Mathematical Foundations of Computer Science 2005
- The Complexity of Counting Functions with Easy Decision Version
- The complexity theory companion
