On intractability of the classUP
From MaRDI portal
Publication:3201755
DOI10.1007/BF02090387zbMath0715.68032MaRDI QIDQ3201755
Publication date: 1991
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
Fault-tolerance and complexity (Extended abstract), On polynomial time one-truth-table reducibility to a sparse set, Reductions to sets of low information content
Cites Work
- Unnamed Item
- On some natural complete operators
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On sparse sets in NP-P
- Relative complexity of checking and evaluating
- A Note on Sparse Complete Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- The density and complexity of polynomial cores for intractable sets
- Complete sets and closeness to complexity classes
- Tally languages and complexity classes