Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345zbMATH Open1156.68384OpenAlexW2494705596MaRDI QIDQ5492867FDOQ5492867

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

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

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)

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
• Mathematical Foundations of Computer Science 2005
• Selfdecomposability and selfsimilarity: a concise primer
• Self-reducibility
• Title not available (Why is that?)

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)