Some descriptive-set-theoretical problems in complexity theory
Summary: We bring some descriptive-set-theoretical problems into complexity theory. We here deal with the uniformization problem and the separation problem. It is shown that 1) there exists an oracle \(A\) such that for some set \(S\in {\mathbf P}[A]\) the uniformizator \(U_ s\) is not in \({\mathbf {NP}}[A]\), 2) there is an oracle \(A\) such that \(\text{Sep} ({\mathbf {NP}} [A])\) does not hold and hence so does not \(\text{Unif} ({\mathbf {coNP}}[A])\), and 3) there is an oracle \(A\) such that \(\text{sep} ({\mathbf{NEXT}} [A])\) does not hold and hence so does not \(\text{Unif} ({\mathbf {coNEXT}} [A])\).
- 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
- Comparing complexity classes
- Descriptive set theory
- 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?)
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1328888)
