Some descriptive-set-theoretical problems in complexity theory (Q1328888)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some descriptive-set-theoretical problems in complexity theory |
scientific article |
Statements
Some descriptive-set-theoretical problems in complexity theory (English)
0 references
1992
0 references
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])\).
0 references
uniformization problem
0 references
separation problem
0 references
oracle
0 references