Some descriptive-set-theoretical problems in complexity theory

DOI10.2977/PRIMS/1195168210zbMath0799.03053OpenAlexW2008067104MaRDI QIDQ1328888

Hisao Tanaka

Publication date: 1992

Published in: Publications of the Research Institute for Mathematical Sciences, Kyoto University (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2977/prims/1195168210

zbMATH Keywords

oracleseparation problemuniformization problem

Mathematics Subject Classification ID

Descriptive set theory (03E15) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptive set theory
• Comparing complexity classes
• Relationships between nondeterministic and deterministic tape complexities
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

This page was built for publication: Some descriptive-set-theoretical problems in complexity theory