Robust reductions

DOI10.1007/s002240000134zbMath0946.68053OpenAlexW4248301608MaRDI QIDQ1125798

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

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)

Related Items

Query-monotonic Turing reductions, Average-case intractability vs. worst-case intractability, Competing provers yield improved Karp-Lipton collapse results