scientific article; zbMATH DE number 176522

MaRDI QIDQ4035688zbMATH OpenFDO

Authors Harry Buhrman, Edith Hemaspaandra, Leen Torenvliet

Publication date 18 May 1993

zbMATH Keywords

bounded reductionscompletenessreducibilitiestruth table

Mathematics Subject Classification ID

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

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

Cited in

(13)

• A comparison of polynomial time completeness notions
• Exponential-time and subexponential-time sets
• On 1-truth-table-hard languages
• The relative power of logspace and polynomial time reductions
• Almost every set in exponential time is P-bi-immune
• Non-uniform reductions
• Reduced measures on the boundary
• scientific article; zbMATH DE number 1722697 (Why is no real title available?)
• scientific article; zbMATH DE number 6479643 (Why is no real title available?)
• Classes of bounded nondeterminism
• Completeness for nondeterministic complexity classes
• scientific article; zbMATH DE number 512801 (Why is no real title available?)
• Almost every set in exponential time is P-bi-immune

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)