Some descriptive-set-theoretical problems in complexity theory

DOI10.2977/PRIMS/1195168210MaRDI QIDQ1328888zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Descriptive set theory and Boolean complexity theory
• COMPLEXITY OF INDEX SETS OF DESCRIPTIVE SET-THEORETIC NOTIONS
• scientific article; zbMATH DE number 1786653
• The descriptive complexity of Helson sets
• On the descriptional complexity of operations on semilinear sets
• scientific article; zbMATH DE number 1342206
• Descriptive set theoretical complexity of randomness notions
• On the computational complexity of defining sets
• Descriptive set theoretic methods in automata theory. Decidability and topological complexity
• On the descriptive complexity of Salem sets

Cites work

• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3073037 (Why is no real title available?)
• Comparing complexity classes
• Descriptive set theory
• Relationships between nondeterministic and deterministic tape complexities
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

Cited in

(2)

• scientific article; zbMATH DE number 1786653 (Why is no real title available?)
• Descriptive set theoretic methods in automata theory. Decidability and topological complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1328888)