scientific article; zbMATH DE number 6691435

DOI10.4230/LIPICS.STACS.2014.590MaRDI QIDQ2965519zbMATH OpenFDO

Authors Alan L. Selman, Dung T. Nguyen

Publication date 3 March 2017

zbMATH Keywords

diagonalizationstructural complexityNEXPautoreducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Autoreducibility of NP-complete sets
• Structural properties of nonautoreducible sets
• Non-reduced automorphism schemes
• Nonautonomous bounded remainder sets
• Autoreducibility of NP-complete sets under strong hypotheses
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Nonautonomous equations and almost reducibility sets
• On nonparadoxical sets
• Nonuniform reductions and NP-completeness

Cited in

(3)

• Autoreducibility of NP-complete sets under strong hypotheses
• Structural properties of nonautoreducible sets
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes

This page was built for publication:

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