On Czerwinski's "$\mathrm{P}\ne \mathrm{NP}$ relative to a $\mathrm{P}$-complete oracle"

Abstract

In this paper, we take a closer look at Czerwinski's "$\mathrm{P}\ne \mathrm{NP}$ relative to a $\mathrm{P}$-complete oracle" [Cze23]. There are (uncountably) infinitely-many relativized worlds where $\mathrm{P}$ and $\mathrm{NP}$ differ, and it is well-known that for any $\mathrm{P}$-complete problem $A$, ${\mathrm{P}}^A\ne {\mathrm{NP}}^A⟺\mathrm{P}\ne \mathrm{NP}$. The paper defines two sets ${\mathrm{D}}_{\mathrm{P}}$ and ${\mathrm{D}}_{\mathrm{NP}}$ and builds the purported proof of their main theorem on the claim that an oracle Turing machine with ${\mathrm{D}}_{\mathrm{NP}}$ as its oracle and that accepts ${\mathrm{D}}_{\mathrm{P}}$ must make $\Theta (2^n)$ queries to the oracle. We invalidate the latter by proving that there is an oracle Turing machine with ${\mathrm{D}}_{\mathrm{NP}}$ as its oracle that accepts ${\mathrm{D}}_{\mathrm{P}}$ and yet only makes one query to the oracle. We thus conclude that Czerwinski's paper [Cze23] fails to establish that $\mathrm{P}\ne \mathrm{NP}$.