On the autoreducibility of functions

DOI10.1007/S00224-008-9127-9zbMATH Open1209.68262OpenAlexW2049926402MaRDI QIDQ970103FDOQ970103

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

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

zbMATH Keywords

reductionsfunction classesautoreducibilitycomplete functionslength-decreasing self-reducibility

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Associative idempotent nondecreasing functions are reducible
• The consequences of eliminating NP solutions
• Finding Optimal Solutions With Neighborly Help.
• Title not available (Why is that?)
• Finding optimal solutions with neighborly help

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)