\(R_{1-tt}^{{\mathcal SN}}\)(NP) distinguishes robust many-one and Turing completeness

DOI10.1007/s002240000090zbMath0896.68060MaRDI QIDQ1387830

Hemaspaandra, Lane A., Edith Hemaspaandra, Harald Hempel

Publication date: 1 October 1998

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

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

zbMATH Keywords

Turing-complete sets

Mathematics Subject Classification ID

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

Related Items

Reductions between disjoint NP-pairs, Query Order