Non-uniform reductions
type: Item
instance of: scholarly article
title: Non-uniform reductions
zbMATH Open document ID: 1206.68129
author: Harry Buhrman
author: Leen Torenvliet
author: Benjamin Hescott
author: S. Homer
published in: Theory of Computing Systems
publication date: 2010-10-06T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5796555
zbMATH Keywords: non-uniform reductions
zbMATH Keywords: reductions with advice
zbMATH Keywords: non-uniform complexity
zbMATH Keywords: NEXP-complete set
zbMATH Keywords: EXP-complete set
zbMATH Keywords: NP-complete set
MaRDI profile type: Publication
full work available at URL: s00224-008-9163-5
OpenAlex ID: W2137788273
cites work: Isomorphisms and 1-L reductions
cites work: Power from Random Strings
cites work: Q3337457
cites work: Q4039803
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: An excursion to the Kolmogorov random strings
cites work: Q3396548
cites work: Completeness for nondeterministic complexity classes
cites work: Q4281494
cites work: The relative power of logspace and polynomial time reductions
cites work: Separating Complexity Classes Using Autoreducibility
cites work: Q4230324
cites work: Complete Problems and Strong Polynomial Reducibilities
cites work: Non-mitotic Sets
cites work: One-way functions and the nonisomorphism of NP-complete sets
cites work: On 1-truth-table-hard languages
cites work: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
cites work: Comparing Reductions to NP-Complete Sets
cites work: Oracles for structural properties: The isomorphism problem and public-key cryptography
cites work: Computability and complexity theory
cites work: The isomorphism conjecture fails relative to a random oracle
cites work: The complexity of optimization problems
cites work: A comparison of polynomial time reducibilities
cites work: Almost every set in exponential time is P-bi-immune
cites work: A comparison of polynomial time completeness notions
DOI: 10.1007/S00224-008-9163-5
Recommended article: Q3304139
Recommended article: Nonuniform reductions and NP-completeness
Recommended article: Non-malleable Reductions and Applications
Recommended article: Q4934278
Recommended article: Reducibility and nonbinding
Recommended article: Partial-Order Reduction
Recommended article: Reductions and quantization
Recommended article: Q4281494
Recommended article: Q4035688
Recommended article: Reducing the complexity of reductions
description: scientific article; zbMATH DE number 5796555