scientific article; zbMATH DE number 6691435

DOI10.4230/LIPICS.STACS.2014.590zbMATH Open1359.68098MaRDI QIDQ2965519FDOQ2965519

Authors: Alan L. Selman, Dung T. Nguyen 

Publication date: 3 March 2017

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

diagonalizationstructural complexityNEXPautoreducibility

Mathematics Subject Classification ID

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

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)