Algorithm for Solving SAT in O(n)
Abstract
This is a novel algorithm that solves SAT in $O(n)$. The approach is as follows: first, reduce any SAT instance (e.g., 3-SAT) to 2-SAT, then solve it using Tarjan's algorithm. The parsing is performed using binary search. The reduction is done correctly.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Constraint Satisfaction and Optimization
Advanced Graph Theory Research
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 6 February 2026
- Language
- EN
- Document type
- Preprint