Some descriptive-set-theoretical problems in complexity theory (Q1328888): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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 | |||
Property / cites work | |||
Property / cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3996675 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Comparing complexity classes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5812175 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Descriptive set theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5573961 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Relationships between nondeterministic and deterministic tape complexities / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 16:39, 22 May 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