Uniformly hard languages.
From MaRDI portal
Publication:1874273
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
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
