Oracle with P=NP, but no many-one completeness in UP, disjNP, and disjConNP

DOI10.4230/LIPICS.MFCS.2022.45MaRDI QIDQ6584044FDOQ6584044

Authors: Anton Ehrmanntraut, Fabian Egidy, Christian Glaßer 

Publication date: 6 August 2024

zbMATH Keywords

computational complexityproof complexitycomplete setsoracle constructionpromise classes

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Oracle with \(\text{P}=\text{NP}\cap\text{coNP}\), but no many-one completeness in UP, disjNP, and disjConNP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6584044)