Some descriptive-set-theoretical problems in complexity theory (Q1328888): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.2977/prims/1195168210 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2008067104 / rank | |||
Normal rank |
Revision as of 01:11, 20 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