Some descriptive-set-theoretical problems in complexity theory (Q1328888): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
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 |
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