Some descriptive-set-theoretical problems in complexity theory (Q1328888): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:57, 5 March 2024
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