Abstract This paper takes graph algorithms as the research carrier and proposes a new classification scheme for computational problems, which differs from traditional frameworks. For some problems, a conclusion holding for constant-sized subgraphs suffices to determine the global answer. For other problems, no constant-sized subgraph can produce a definitive yes/no judgment of the global property. This binary classification carries substantial theoretical significance. This work proves that most problems in class P are locally computable via constant-sized subgraphs, while most NP problems cannot be solved using any fixed-size local subgraph. This dichotomy creates clear computational distinctions under deterministic Turing machines. Our analysis relies on two foundational tools of computer science and information theory: Turing machines and Kolmogorov complexity, alongside elementary results from graph theory and random graph theory. No advanced background knowledge is required for readers.
Guojun Liu (Sun,) studied this question.