Oracle with \(\text{P}=\text{NP}\cap\text{coNP}\), but no many-one completeness in UP, disjNP, and disjConNP (Q6584044)
From MaRDI portal
!
WARNING
This is the item page for this Wikibase entity, intended for internal use and editing purposes.
Please use the normal view instead:
scientific article; zbMATH DE number 7893083
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Oracle with \(\text{P}=\text{NP}\cap\text{coNP}\), but no many-one completeness in UP, disjNP, and disjConNP |
scientific article; zbMATH DE number 7893083 |
Statements
Oracle with \(\text{P}=\text{NP}\cap\text{coNP}\), but no many-one completeness in UP, disjNP, and disjConNP (English)
0 references
6 August 2024
0 references
computational complexity
0 references
promise classes
0 references
proof complexity
0 references
complete sets
0 references
oracle construction
0 references
