On hard instances
From MaRDI portal
Publication:1575555
DOI10.1016/S0304-3975(98)00262-XzbMath0947.68079MaRDI QIDQ1575555
Publication date: 21 August 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00262-x
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Cites Work
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On resource-bounded instance complexity
- Random strings make hard instances
- On Reducibility to Complex or Sparse Sets
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- New Collapse Consequences of NP Having Small Circuits
- Instance complexity
- SPARSE Reduces Conjunctively to TALLY
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item