On the autoreducibility of functions
type: Item
instance of: scholarly article
title: On the autoreducibility of functions
zbMATH Open document ID: 1209.68262
author: Piotr Faliszewski
author: Ogihara, Mitsunori
published in: Theory of Computing Systems
publication date: 2010-05-10T00:00:00Z
full work available at URL: http://hdl.handle.net/1802/4042
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5706000
zbMATH Keywords: autoreducibility
zbMATH Keywords: length-decreasing self-reducibility
zbMATH Keywords: reductions
zbMATH Keywords: function classes
zbMATH Keywords: complete functions
MaRDI profile type: Publication
OpenAlex ID: W2049926402
cites work: On hiding information from an oracle
cites work: Q3337457
cites work: Self-reducibility
cites work: On being incoherent without being very hard
cites work: Q4293543
cites work: \(p\)-selective self-reducible sets: a new characterization of P
cites work: Separating Complexity Classes Using Autoreducibility
cites work: Random-Self-Reducibility of Complete Sets
cites work: The power of adaptiveness and additional queries in random-self- reductions
cites work: Gap-definable counting classes
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Mathematical Foundations of Computer Science 2005
cites work: On the closure of certain function classes under integer division by polynomially-bounded functions
cites work: Closure properties and witness reduction
cites work: The complexity theory companion
cites work: Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
cites work: On counting and approximation
cites work: The complexity of optimization problems
cites work: Mitotic recursively enumerable sets
cites work: Relativization of questions about log space computability
cites work: A comparison of polynomial time reducibilities
cites work: Q3210157
cites work: A complexity theory for feasible closure properties
cites work: The Complexity of Counting Functions with Easy Decision Version
cites work: Q4298260
cites work: Complexity classes defined by counting quantifiers
cites work: The complexity of computing the permanent
cites work: Q4942628
cites work: The complexity of combinatorial problems with succinct input representation
cites work: Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
cites work: #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
DOI: 10.1007/S00224-008-9127-9
description: scientific article; zbMATH DE number 5706000