The Structural Burden of NP Computation

The definition of nondeterministic polynomial-time computation expresses acceptance as the existence of an accepting computation history among a family of candidates generated by nondeterministic choices. The Cook–Levin theorem shows that this structure is preserved when NP computations are encoded as Boolean satisfiability instances: the tableau constraints describe the family of valid computation histories, while the acceptance condition selects those histories that correspond to successful computations.This paper examines this observation from a structural perspective. We introduce the notion of a Structural Fidelity Representation (SFR) to make explicit the family of candidate computation histories induced by nondeterministic computation.We then formulate the Formula Location Problem (FLP), which isolates the residual task of determining whether this family contains an accepting member. Because the definition of NP is based on nondeterministic computation and the Cook–Levin construction faithfully encodes that computation, this structural burden appearsuniformly across all NP problems.Finally, we introduce the abstraction of an Accepting Family Selector (AFS) to describe the capability that a deterministic polynomial-time solution to NP-complete problems would need to realize: locating an accepting member of the candidate family without exhaustively traversing the exponential search space. The goal of thepaper is not to resolve the P versus NP question, but to clarify the structural form of the computational burden that any such resolution would need to address