A Universal Exploration-Based Classification of Algorithms in NP

This paper proposes a simple and universal way to compare algorithms for NP problems based on how much of the underlying solution space they must explore. Instead of focusing on running time or implementation details, the approach looks at the witness space induced by the standard NP verification model and measures how many candidate solutions an algorithm needs to distinguish, either by explicitly testing them or by implicitly ruling them out through reasoning or pruning. From this idea, the paper introduces normalized asymptotic descriptors that classify algorithms into polynomial, subexponential, or exponential exploration regimes, independently of the algorithmic paradigm used. This makes it possible to compare brute-force search, backtracking, heuristic branching, and other approaches within a single conceptual framework. The framework is illustrated using the graph k-colorability problem, where it captures the behavior of classical algorithms ranging from exhaustive search to pruning-based methods such as DSATUR. The goal of the work is not to propose new algorithms or to resolve the P vs NP question, but to provide a clean and intuitive language for reasoning about algorithmic progress in NP problems and for organizing existing and future approaches around their exploration behavior.