On the autoreducibility of functions

DOI10.1007/S00224-008-9127-9MaRDI QIDQ970103zbMATH OpenOpenAlexFDO

Authors Piotr Faliszewski, Ogihara, Mitsunori

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

zbMATH Keywords

reductionsfunction classesautoreducibilitycomplete functionslength-decreasing self-reducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 4191094 (Why is no real title available?)
• scientific article; zbMATH DE number 3869312 (Why is no real title available?)
• scientific article; zbMATH DE number 578252 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1414291 (Why is no real title available?)
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• A comparison of polynomial time reducibilities
• A complexity theory for feasible closure properties
• Closure properties and witness reduction
• Complexity classes defined by counting quantifiers
• Computational Complexity of Probabilistic Turing Machines
• Gap-definable counting classes
• Mathematical Foundations of Computer Science 2005
• Mitotic recursively enumerable sets
• On being incoherent without being very hard
• On counting and approximation
• On hiding information from an oracle
• On the closure of certain function classes under integer division by polynomially-bounded functions
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Random-Self-Reducibility of Complete Sets
• Relativization of questions about log space computability
• Self-reducibility
• Separating Complexity Classes Using Autoreducibility
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• The Complexity of Counting Functions with Easy Decision Version
• The complexity of combinatorial problems with succinct input representation
• The complexity of computing the permanent
• The complexity of optimization problems
• The complexity theory companion
• The power of adaptiveness and additional queries in random-self- reductions
• \(p\)-selective self-reducible sets: a new characterization of P

Cited in

(7)

• Associative idempotent nondecreasing functions are reducible
• Finding optimal solutions with neighborly help
• scientific article; zbMATH DE number 1759426 (Why is no real title available?)
• Finding Optimal Solutions With Neighborly Help.
• 2-local random reductions to 3-valued functions
• The consequences of eliminating NP solutions
• Mathematical Foundations of Computer Science 2005

This page was built for publication: On the autoreducibility of functions

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