2023/12/07 by Michael C. Chavrimootoo, Chavrimootoo, Michael C., Tran Duy Anh Le +5
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2312.04395
openalex publication_date 2023/12/07 · openalex created_date 2023/12/09 · openalex updated_date 2026/07/28
In this paper, we take a closer look at Czerwinski's "\rm P≠\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 PA ≠ \rm NPA \iff \rm P≠ \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 Θ(2n) 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 ≠ \rm NP.