scientific article; zbMATH DE number 176522

zbMATH Open0773.68029MaRDI QIDQ4035688FDOQ4035688

Authors: Harry Buhrman, Edith Hemaspaandra, Leen Torenvliet 

Publication date: 18 May 1993

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

Recommendations

• scientific article; zbMATH DE number 512801
• Completeness for nondeterministic complexity classes
• The relative power of logspace and polynomial time reductions
• Separating NP-completeness notions under strong hypotheses
• scientific article; zbMATH DE number 1072532

zbMATH Keywords

completenesstruth tablereducibilitiesbounded reductions

Mathematics Subject Classification ID

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

Cited In (12)

• Almost every set in exponential time is P-bi-immune
• A comparison of polynomial time completeness notions
• On 1-truth-table-hard languages
• Completeness for nondeterministic complexity classes
• Classes of bounded nondeterminism
• Non-uniform reductions
• The relative power of logspace and polynomial time reductions
• Exponential-time and subexponential-time sets
• Almost every set in exponential time is P-bi-immune
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reduced measures on the boundary

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 Q4035688)