Robust reductions

DOI10.1007/S002240000134MaRDI QIDQ1125798zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Lane A. Hemaspaandra, Gerd Wechsung

Publication date 7 March 2000

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002240000134

zbMATH Keywords

robust reductions

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1222831
• ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
• scientific article; zbMATH DE number 4208065

Cited in

(8)

• Competing provers yield improved Karp-Lipton collapse results
• Query-monotonic Turing reductions
• scientific article; zbMATH DE number 4208065 (Why is no real title available?)
• Guyan reduction
• ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
• scientific article; zbMATH DE number 1222831 (Why is no real title available?)
• Cohesive avoidance and strong reductions
• Average-case intractability vs. worst-case intractability

This page was built for publication: Robust reductions

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