Structural Separation and Semantic Incompatibility in the P P vs. N ​ P NP Problem: Computational Complexity Analysis with Construction Defining Functionality

Yumiko Nishiyama · 2025

Read Structural Separation and Semantic Incompatibility in the P P vs. N ​ P NP Problem: Computational Complexity Analysis with Construction Defining Functionality by Yumiko Nishiyama (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-22995.txt.

Introduction

Yumiko Nishiyama argues that the hard core of NP problems lies in the syntax of SAT itself. SAT, the Boolean satisfiability problem, was the first problem shown NP-complete. It now serves as the yardstick for hardness proofs. Nishiyama flips that view. Within a framework she calls CDF, she asks whether the structure of 3SAT creates the blow-up seen across NP problems.

On this reading, SAT is not just a benchmark but the archetype that induces NP-type hardness. The P versus NP question then rests on how problem syntax is generated. Recursive and non-local builds in 3SAT mark the line between easy and hard tasks. The paper is a position piece, not a proof.

Catalog record

CREATORYumiko Nishiyama
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-22995

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Structural Separation and Semantic Incompatibility in the P P vs. N ​ P NP Problem: Computational Complexity Analysis with Construction Defining Functionality Yumiko Nishiyama Abstract We introduce the Construction Defining Functionality (CDF) framework, a structural approach to computational complexity grounded in a rigorous distinction between syntax and semantics aligned with mathematical logic. By analyzing how syntactic definitions transform into semantic interpretations—constructed within propositional logic—and further into logical consequences, CDF characterizes problems according to the coherence and complexity of these layered mappings. The framework identifies two fundamental classes: problems with stable, compositional generative structures ( ComCDF ) that allow polynomial-time resolution, and problems exhibiting intensional, non-local constructions leading to exponential semantic explosion ( ExpCDF ). This semantic explosion originates from the combinatorial complexity inherent in propositional semantic spaces induced by syntactic recursion and dependencies. Our results suggest that the separation of 𝖯 \mathsf{P} and 𝖭𝖯 \mathsf{NP} reflects a profound structural divide in the generative principles of problems themselves—beyond mere resource bounds. And through a canonical example such as 2-SAT versus 3-SAT, we illustrate how logical representation generates semantic complexity of problem.The CDF framework thus offers a unified foundation bridging syntax, semantics, and logic, opening new avenues for complexity theory and algorithm design. 1 Introduction 1.1 Basic Concept of Construction Defining Functionality (CDF) In computational theory and logic, the distinction between intensional and extensional perspectives has long shaped our understanding of functions and problem representations. Extensional approaches characterize functions through observable input-output behavior—what a function does . Intensional perspectives, by contrast, focus on the internal syntactic rules or constructions that generate a function—what a function is . While extensional models have provided the foundation for classical complexity theory, they often obscure the structural differences that make certain problems computationally hard. In particular, many \mathsf{NP} -complete problems resist extensional decomposition, not merely because they are large or complex, but because their internal semantic structure lacks the kind of compositional coherence that makes algorithmic reasoning tractable. In this work, we introduce the Construction Defining Functionality (CDF) framework as a formal model for analyzing the layered structure of computational problems. CDF is designed to capture both the intensional constructions that define a problem and the extensional behaviors that emerge from them, using a logical and topological method. At the heart of CDF is a tripartite architecture: • Syntactic space ( S_{\mathrm{syn}}(f) ) — the formal definition or rule specifying a function or problem instance; • Semantic space ( S_{\mathrm{sem}}(f) ) — the space of configurations or models that satisfy the syntactic constraints; • Logical space ( S_{\mathrm{log}}(f) ) — the inferential outcomes or decision properties derived from the semantics. These spaces are connected via structural mappings: \alpha_{f}:S_{\mathrm{syn}}(f)\to S_{\mathrm{sem}}(f),\quad\beta_{f}:S_{\mathrm{sem}}(f)\to S_{\mathrm{log}}(f),\quad\gamma_{f}:S_{\mathrm{syn}}(f)\to S_{\mathrm{log}}(f). This layered generativity can be visualized as the following diagram: {\lx@inpgf@ignorespaces\mathcal{S}_{\mathrm{syn}}(f)} {\lx@inpgf@ignorespaces\mathcal{S}_{\mathrm{sem}}(f)} {\lx@inpgf@ignorespaces\mathcal{S}_{\mathrm{log}}(f)} \scriptstyle{\lx@inpgf@ignorespaces\alpha_{f}} \scriptstyle{\lx@inpgf@ignorespaces\gamma_{f}} \scriptstyle{\lx@inpgf@ignorespaces\beta_{f}} The coherence or instability of these mappings reflects how well a problem’s syntactic definition supports compositional reasoning. In this way, the CDF framework identifies a new axis of classification for problems: whether their internal structure supports stable semantic growth and logical deduction ( ComCDF ), or whether it induces recursive, explosive entanglement ( ExpCDF ). We show that this distinction aligns strikingly with the boundary between classes such as \mathsf{P} and \mathsf{NP} . Problems like 2-SAT exhibit localized, decomposable constructions whose semantic spaces remain tame. In contrast, problems like 3-SAT generate complex, non-local interactions among constraints, leading to exponential semantic explosion and breakdown of compositional coherence. The primary contribution of this paper is to develop and apply the CDF framework to reveal structural reasons behind computational tractability and intractability. By distinguishing between external behavior and internal construction, CDF offers a complementary and potentially foundational perspective on computational complexity—one grounded not in runtime bounds, but in the geometry and logic of how problems are built. 1.2 Intensionality and Extensionality in CDF The notions of intensionality and extensionality in the CDF framework differ from those in classical set theory. In set theory, the distinction is mainly representational: • Intensional definitions describe a set via a property. • Extensional definitions list the elements of the set. By contrast, CDF interprets intensionality and extensionality as structural and generative: • Intensionality refers to the internal rules or definitions that generate system behavior. • Extensionality refers to the observable outcomes or behaviors resulting from that internal structure. This distinction highlights how simple behaviors can arise from complex internal mechanisms. In CDF, intensionality and extensionality are not just different ways of expressing the same object—they represent different levels of abstraction and causality within formal systems. 1.3 Syntax and Semantics in the CDF Framework The Construction Defining Functionality (CDF) framework integrates a clear structural distinction between syntactic and semantic reasoning, reflecting classical logical theory while elucidating computational complexity origins. 1.3.1 Classical Syntax–Semantics Distinction • Syntax concerns formal symbolic manipulations governed by inference rules, focusing on provability and derivations without regard to meaning or truth values. • Semantics evaluates the truth or falsity of propositions under interpretations or models, thus addressing meaning externally to syntactic formalisms. This classical distinction underpins the semantic explosion phenomenon observed in complex computational problems. 1.3.2 CDF Mappings Corresponding to Syntax and Semantics The CDF framework models this distinction explicitly through its structural mappings: \begin{cases}\alpha_{f}:S_{\mathrm{syn}}\to S_{\mathrm{sem}},\\ \beta_{f}:S_{\mathrm{sem}}\to S_{\mathrm{log}},\\ \gamma_{f}:S_{\mathrm{syn}}\to S_{\mathrm{log}}.\end{cases} Perspective Role in CDF Syntax \gamma_{f} : Formal logical inference and provability performed directly on syntactic constructs, representing proof-theoretic reasoning. Semantics \alpha_{f} , \beta_{f} : Translation from syntax to semantic structures, and from semantics to logical evaluation, representing model-theoretic reasoning based on truth and interpretation. Table 1 : Syntax and semantics in the CDF framework 1.3.3 Propositional Logic as the Semantic Foundation Semantics in CDF is constructed via propositional logic, where S_{\mathrm{sem}}\subseteq\mathcal{L}_{\mathrm{prop}}, the space of propositional formulas. This reflects the classical model-theoretic view where meanings correspond to truth assignments of propositions. The complexity inherent in propositional logic—especially as syntactic structures become deeply recursive or intensional—directly leads to semantic explosion: an exponential growth in the number and interdependencies of propositional interpretations that must be considered. 1.3.4 Syntactic vs Semantic Reasoning and Complexity In the CDF framework, the contrast between syntactic and semantic reasoning surfaces naturally: • Syntactic reasoning ( \gamma_{f} ) operates by manipulating formal proofs and derivations. While compositional and stable syntactic structures allow polynomial-time reasoning, complex recursive or intensional definitions quickly undermine compositionality, causing syntactic reasoning to become fragile. • Semantic reasoning ( \alpha_{f} , \beta_{f} ) evaluates truth across propositional configurations. As the syntactic input structure increases, the semantic space grows combinatorially, leading to exponential computational complexity—a core source of the semantic explosion phenomenon. Thus, the CDF mappings illuminate the boundary between syntactic tractability and semantic intractability, framing semantic explosion as a structural consequence that syntactic forms applied to complex propositional logic. 2 Basic Procedure of CDF framework This section formalizes the core concepts of the CDF framework by defining the structural space generated by a function and the interrelated components that capture its syntactic, semantic, and logical properties. Definition 2.1 (Structural Property Sets of CDF) . Let f:X\to Y be a function. The Construction Defining Functionality (CDF) of f is defined as the triple of structural property sets: S(f)=\left(S_{\mathrm{syn}}(f),\ S_{\mathrm{sem}}(f),\ S_{\mathrm{log}}(f)\right), where • S_{\mathrm{syn}}(f) is the syntactic property set , describing symbolic patterns and generative structure of f ’s operation. •

Read the complete text