Re:A Polynomial Time Algorithm for 3SAT (P=NP?!)
by rmujica on Monday July 19, 2021 @12:28PM
(#27884455)
Abstract:
> By creating new concepts and methods—the checking tree, long unit path, direct contradiction unit pair, indirect contradiction unit pair, additional contradiction unit pair, two-unit layer and three-unit layer—we successfully transform solving a 3SAT problem to solving 2SAT problems in polynomial time.
> Each time, we add only one layer of the three-unit layers to the two-unit layers to calculate 2SAT paths, respectively.
> The key is as follows: in each 2SAT path, any two units cannot be a direct contradiction unit pair and cannot be an indirect contradiction unit pair and additional contradiction unit pair.
> This guarantees that all of the 2SAT paths we got, respectively, can shape at least one long path without contradictions.
> By creating new concepts and methods—the checking tree, long unit path, direct contradiction unit pair, indirect contradiction unit pair, additional contradiction unit pair, two-unit layer and three-unit layer—we successfully transform solving a 3SAT problem to solving 2SAT problems in polynomial time.
> Each time, we add only one layer of the three-unit layers to the two-unit layers to calculate 2SAT paths, respectively.
> The key is as follows: in each 2SAT path, any two units cannot be a direct contradiction unit pair and cannot be an indirect contradiction unit pair and additional contradiction unit pair.
> This guarantees that all of the 2SAT paths we got, respectively, can shape at least one long path without contradictions.
> Thus, we proved that NP = P.