Solving NP-complete Problems Efficiently

Abstract

The P versus NP problem is a fundamental question in computer science. It asks whether problems whose solutions can be quickly verified can also be quickly solved. Here, "quickly" refers to computational time that grows proportionally to the size of the input (polynomial time). While the problem's roots trace back to a 1955 letter from John Nash, its formalization is attributed to Stephen Cook and Leonid Levin. Despite extensive research, a definitive answer remains elusive. Closely tied to this is the concept of NP-completeness. If a single NP-complete problem could be solved efficiently, it would imply that all problems in NP can be solved efficiently, proving that P equals NP. Garey and Johnson defined K-CLOSURE such that for any edge $(u, v)$ in the directed graph, either node $u$ is in the set $V'$ or node $v$ is not in $V'$. This implies that either both nodes are in $V'$ or both are not in $V'$. Our previous work in IPI Letters presented a polynomial-time algorithm for K-CLOSURE. While no errors have been identified in this work, many believe that Garey and Johnson's original definition was incorrect, and their citation of Queyranne was a misunderstanding. Many argue that the empty set serves as a simple counterexample to Garey and Johnson's definition of K-CLOSURE. This paper proposes that K-CLOSURE is actually an NP-complete problem, which would imply that P equals NP.