Uniformly hard languages.
type: Item
instance of: scholarly article
title: Uniformly hard languages.
zbMATH Open document ID: 1051.68091
DOI: 10.1016/S0304-3975(02)00810-1
published in: Theoretical Computer Science
publication date: 2003-05-25T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1915464
zbMATH Keywords: minimal recursive sets
author: Rodney G. Downey
author: Lance Fortnow
MaRDI profile type: Publication
cites work: Q3337458
cites work: Q3778006
cites work: The theory of the polynomial many-one degrees of recursive sets is undecidable
cites work: \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
cites work: A note on a theorem by Ladner
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: A note on structure and looking back applied to the relative complexity of computable functions
cites work: Nondiamond theorems for polynomial time reducibility
cites work: Q4198056
cites work: Minimal degrees for polynomial reducibilities
cites work: Q4526985
cites work: Q4142699
cites work: On the Structure of Polynomial Time Reducibility
cites work: A comparison of polynomial time reducibilities
cites work: On the structure of sets in NP and other complexity classes
cites work: Polynomial and abstract subrecursive classes
cites work: Hardness vs randomness
cites work: Q3312209
cites work: A uniform approach to obtain diagonal sets in complexity classes
cites work: On the theory of the PTIME degrees of the recursive sets
full work available at URL: s0304-3975(02)00810-1
OpenAlex ID: W2036633410
description: scientific article; zbMATH DE number 1915464