On intractability of the classUP

DOI10.1007/BF02090387MaRDI QIDQ3201755zbMATH OpenFDO

Authors Osamu Watanabe

Publication date 1991

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

Full work available at URL https://doi.org/10.1007/BF02090387

zbMATH Keywords

one-way functionspolynomial time reducibilitysparse sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On polynomial time one-truth-table reducibility to a sparse set
• One-way functions and circuit complexity
• Complexity classes without machines: on complete languages for UP
• On one-way functions and polynomial-time isomorphisms
• scientific article; zbMATH DE number 3990863

Cites work

• A Note on Sparse Complete Sets
• Complete sets and closeness to complexity classes
• scientific article; zbMATH DE number 4070309 (Why is no real title available?)
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• On some natural complete operators
• On sparse sets in NP-P
• Relative complexity of checking and evaluating
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Tally languages and complexity classes
• The density and complexity of polynomial cores for intractable sets

Cited in

(7)

• Complexity classes without machines: on complete languages for UP
• On polynomial time one-truth-table reducibility to a sparse set
• Near-Testable Sets
• Fault-tolerance and complexity (extended abstract)
• Reductions to sets of low information content (extended abstract)
• scientific article; zbMATH DE number 3057871 (Why is no real title available?)
• A note on quadratic residuosity and UP

This page was built for publication: On intractability of the classUP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3201755)