Uniformly hard languages.

DOI10.1016/S0304-3975(02)00810-1zbMath1051.68091OpenAlexW2036633410MaRDI QIDQ1874273

Lance J. Fortnow, Rodney G. Downey

Publication date: 25 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00810-1

zbMATH Keywords

minimal recursive sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

The Birth and Early Years of Parameterized Complexity ⋮ Robust simulations and significant separations ⋮ Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking ⋮ Complexity with Rod ⋮ The complexity of unions of disjoint sets ⋮ Properties of uniformly hard languages

Cites Work

• On the theory of the PTIME degrees of the recursive sets
• A note on a theorem by Ladner
• A note on structure and looking back applied to the relative complexity of computable functions
• On the structure of sets in NP and other complexity classes
• A uniform approach to obtain diagonal sets in complexity classes
• Nondiamond theorems for polynomial time reducibility
• A comparison of polynomial time reducibilities
• Polynomial and abstract subrecursive classes
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• Minimal degrees for polynomial reducibilities
• On the Structure of Polynomial Time Reducibility
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The theory of the polynomial many-one degrees of recursive sets is undecidable
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item