Optimal algorithms for co-NP-sets and the EXP\(\overset{!}{ = }\)NEXP problem

DOI10.1007/BF01157564zbMath0800.68444MaRDI QIDQ1178072

O. V. Verbitskiĭ

Publication date: 26 June 1992

Published in: Mathematical Notes (Search for Journal in Brave)

zbMATH Keywords

Turing machine

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Unnamed Item

This page was built for publication: Optimal algorithms for co-NP-sets and the EXP\(\overset{!}{ = }\)NEXP problem