Structural properties of nonautoreducible sets

DOI10.1145/2898440MaRDI QIDQ4973856zbMATH OpenOpenAlexWikidataFDO

Authors Alan L. Selman, Dung T. Nguyen

Publication date 6 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2898440

zbMATH Keywords

autoreducibilitydiagonalizationNEXPstructural complexity

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 6691435
• Autoreducibility of complete sets for log-space and polynomial-time reductions
• Autoreducibility of NP-complete sets
• Autoreducibility of NP-complete sets under strong hypotheses
• Separating Complexity Classes Using Autoreducibility

Cited in

(4)

• On being incoherent without being very hard
• scientific article; zbMATH DE number 6691435 (Why is no real title available?)
• scientific article; zbMATH DE number 1222582 (Why is no real title available?)
• scientific article; zbMATH DE number 540524 (Why is no real title available?)

This page was built for publication: Structural properties of nonautoreducible sets

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