arXiv:2405.08051cs.CC
P=NP
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
This paper investigates an extremely classic NP-complete problem: How to determine if a graph G, where each vertex has a degree of at most 4, can be 3-colorable(The research in this paper focuses on graphs G that satisfy the condition where the degree of each vertex does not exceed 4. To conserve space, it is assumed throughout the paper that graph G meets this condition by default.). The author has meticulously observed the relationship between the coloring problem and semidefinite programming, and has creatively constructed the corresponding semidefinite programming problem R(G) for a given graph G. The construction method of R(G) refers to Theorem 1.1 in the paper. I have obtained and proven the conclusion: A graph G is 3-colorable if and only if the objective function of its corresponding optimization problem R(G) is bounded, and when the objective function is bounded, its minimum value is 0.
This is fantastic work. The focus on a local, sandboxed execution layer is a huge piece of the puzzle for a private AI workspace. The `coderunner` tool looks incredibly useful. A complementary challenge is the knowledge layer: making the AI aware of your personal data (emails…
andylizfView on HNParent context