r/compsci • • 16h ago

Proving P = NP using Tarjans algorithm on 3SAT implication chains with zero backtracking

0 Upvotes

I wanted to look at P vs NP purely through the lens of foundational data structures and standard graph algorithms.

Instead of trying to convert 3SAT into 2SAT, I broke the 3SAT clauses down into simple, direct implication tracks. These implications naturally chain together wherever the ending variable of one statement matches the starting variable of the next.

By running Tarjans Strongly Connected Components algorithm directly on this network of tracks, the components reveal the truth assignments. Because of the way the paths connect, the algorithm evaluates everything in a forward pass with absolutely zero backtracking or branching required. This drops the total evaluation into polynomial time, proving that P = NP.

The paper is fully formatted in LaTeX and safely hosted on Zenodo with a permanent, time-stamped DOI. All the steps are laid out in the PDF. Let me know what you think:https://doi.org/10.5281/zenodo.23696546


r/compsci • • 1h ago

We’re looking at the P vs. NP problem all wrong. It’s not a math puzzle; it’s a 1D physical limitation

Thumbnail
• Upvotes

Your thoughts are appreciated. Your words, even more so.