Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345MaRDI QIDQ5492867zbMATH OpenOpenAlexFDO

Authors Piotr Faliszewski, Ogihara, Mitsunori

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the autoreducibility of functions
• Autoreducibility of complete sets for log-space and polynomial-time reductions
• Separating Complexity Classes Using Autoreducibility
• Autoreducibility of NP-complete sets under strong hypotheses
• Autoreducibility of NP-complete sets

Cited in

(9)

• Sparse selfreducible sets and nonuniform lower bounds
• Autoreducibility of NP-complete sets
• Length-increasing reductions for PSPACE-completeness
• Remarks on the selfdecomposability and new examples
• On the autoreducibility of functions
• Selfdecomposability and selfsimilarity: a concise primer
• Mathematical Foundations of Computer Science 2005
• Self-reducibility
• scientific article; zbMATH DE number 4022646 (Why is no real title available?)

This page was built for publication: Mathematical Foundations of Computer Science 2005

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