On hard instances

DOI10.1016/S0304-3975(98)00262-XzbMath0947.68079OpenAlexW2089937401MaRDI QIDQ1575555

Martin Mundhenk

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

zbMATH Keywords

instance complexityhard instances

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: On hard instances