On Czerwinski's '${\rm P} \neq {\rm NP}$ relative to a ${\rm P}$-complete oracle'
2023
Online
report
In this paper, we take a closer look at Czerwinski's "${\rm P}\neq{\rm NP}$ relative to a ${\rm P}$-complete oracle" [Cze23]. There are (uncountably) infinitely-many relativized worlds where ${\rm P}$ and ${\rm NP}$ differ, and it is well-known that for any ${\rm P}$-complete problem $A$, ${\rm P}^A \neq {\rm NP}^A \iff {\rm P}\neq {\rm NP}$. The paper defines two sets ${\rm D}_{\rm P}$ and ${\rm D}_{\rm NP}$ and builds the purported proof of their main theorem on the claim that an oracle Turing machine with ${\rm D}_{\rm NP}$ as its oracle and that accepts ${\rm D}_{\rm P}$ must make $\Theta(2^n)$ queries to the oracle. We invalidate the latter by proving that there is an oracle Turing machine with ${\rm D}_{\rm NP}$ as its oracle that accepts ${\rm D}_{\rm P}$ and yet only makes one query to the oracle. We thus conclude that Czerwinski's paper [Cze23] fails to establish that ${\rm P} \neq {\rm NP}$.
Titel: |
On Czerwinski's '${\rm P} \neq {\rm NP}$ relative to a ${\rm P}$-complete oracle'
|
---|---|
Autor/in / Beteiligte Person: | Chavrimootoo, Michael C. ; Le, Tran Duy Anh ; Reidy, Michael P. ; Smith, Eliot J. |
Link: | |
Veröffentlichung: | 2023 |
Medientyp: | report |
Schlagwort: |
|
Sonstiges: |
|