On the Inevitable Logical Self-Reference Arising from Circumventing Non-Deterministic Reasoning

This paper investigates the structural constraints of deterministic Turing machines for solving the maximum clique problem. Two core results are proven herein: First, due to the constant-bit constraint on single-step vision of Turing machines and the high Kolmogorov complexity of random graphs, single-step computation cannot acquire sufficient information to determine the global maximum clique structure. The verification sets constructed in this paper demonstrate that no critical substructure exists, and it is impossible to determine the maximum clique solely by reading such critical substructures. Second, even when leveraging the so-called global effects, the problem of deciding whether a vertex belongs to some maximum clique still falls into a quasi-logical self-referential cycle: decision relies on construction, and construction relies on decision. These two obstacles jointly form an impenetrable barrier. When solving the maximum clique problem on a deterministic Turing machine, one must either adopt multi-round guessing (equivalent to enumerating all maximal cliques) or become trapped in the self-referential cycle. This paper does not claim to resolve the P vs. NP problem, yet it lays out two mandatory core questions that any attempt to design an efficient algorithm must address.