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

DOI10.1007/S002240000090zbMath0896.68060OpenAlexW2057527249MaRDI QIDQ1387830

Hemaspaandra, Lane A., Harald Hempel, Edith Hemaspaandra

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

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

Related Items (3)

Query order in the polynomial hierarchy ⋮ Reductions between disjoint NP-pairs ⋮ Query Order

This page was built for publication: \(R_{1-tt}^{{\mathcal SN}}\)(NP) distinguishes robust many-one and Turing completeness