Models of Computation and their Limits: Turing Machines, Nondeterminism and the P vs NP Hypothesis

Abstract

The article explores fundamental concepts of computational complexity theory, with a focus on the relationship between the complexity classes P and NP and the Boolean satisfiability problem (SAT) as a central NP-complete problem. Theoretical foundations are introduced through models of computation, particularly deterministic and nondeterministic Turing machines, which formalize the limits of efficient computation. A significant part of the work is dedicated to SAT, including its role in complexity theory and its practical relevance. Classical and modern solving techniques are presented, with emphasis on the DPLL algorithm and its extension, CDCL, which form the basis of modern SAT solvers. To illustrate the practical implications of these concepts, the graph coloring problem is used as a case study. It is approached from two perspectives: a reduction to SAT and a direct backtracking-based algorithm. The two methods are implemented and experimentally compared in terms of execution time on randomly generated graph instances with varying sizes and densities. The experimental results show that the direct approach generally outperforms the SATbased formulation in the analyzed instances, while the SAT approach provides a more general theoretical framework. The study highlights the trade-off between generality and efficiency in algorithm design, as well as the practical challenges associated with NP-complete problems. CZU: 330.43; JEL: C00, C60, C63