A Critique of Deng's "P=NP"

Key Points

Deng's claim of a polynomial-time algorithm for 3-coloring is undermined by critical errors.
The analysis reveals a mix-up between subgraphs and induced subgraphs that invalidates the proof.
The semidefinite program presented does not correctly function for all graphs, especially non-3-colorable ones.
Deng's approach to the NP-complete problem fails to hold under scrutiny, indicating the complexity remains unresolved.

Abstract

In this paper, we critically examine Deng's "P=NP" Den24. The paper claims that there is a polynomial-time algorithm that decides 3-coloring for graphs with vertices of degree at most 4, which is known to be an NP-complete problem. Deng presents a semidefinite program with an objective function that is unboundedly negative if the graph is not 3-colorable, and a minimum of 0 if the graph is 3-colorable. Through detailed analysis, we find that Deng conflates subgraphs with induced subgraphs, leading to a critical error which thereby invalidates Deng's proof that P=NP.

Read Full Paperexternally

Bookmark

View Full Paper

Cite This Study

Humphreys et al. (Fri,) studied this question.

synapsesocial.com/papers/68de5d9c83cbc991d0a202c5 https://doi.org/https://doi.org/10.48550/arxiv.2507.09018

Bookmark

View Full Paper