On intractability of the classUP

DOI10.1007/BF02090387zbMath0715.68032MaRDI QIDQ3201755

Osamu Watanabe

Publication date: 1991

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

sparse setsone-way functionspolynomial time reducibility

Mathematics Subject Classification ID

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