A Distorted-Monoidal Reformulation of the Natural Proofs Barrier

A Distorted-Monoidal Reformulation of the Natural Proofs Barrier Joaquim Reizi Higuchi December 12, 2025 Abstract We formalize a categorical “distorted monoidal” framework (DMT) intended to capture irreversible computational structure via a non-invertible distortion operator and a monoidal syntax of compositional reasoning. Within this setting we define a class of DMT-natural lower-bound methods, characterized by (i) constructivity, (ii) largeness, and (iii) invariance under distortion. We then prove a barrier theorem: assuming the existence of exponentially hard pseudorandom functions, no DMT-natural method can yield superpolynomial circuit lower bounds against P/poly (and hence such a method cannot separate P from NP). The proof is a reduction to the Razborov–Rudich Natural Proofs barrier, showing that any DMT-natural property induces a classical natural property. This paper does not prove P = NP; it explains, in a precise sense, why a broad family of “distortion-invariant” strategies cannot succeed under standard cryptographic hardness assumptions. 1 Introduction A central difficulty in circuit complexity is to prove strong lower bounds for explicit Boolean functions, particularly those sufficient to separate P from NP. The celebrated Natural Proofs framework of Razborov and Rudich identifies a wide class of lower-bound techniques (“natural proofs”) and shows that, under standard pseudorandomness assumptions, such techniques cannot prove superpolynomial lower bounds for general circuits [1]. Subsequent work has clarified variants and connections to derandomization and lower bounds [3,2]. Motivated by categorical semantics of computation and string-diagrammatic reasoning (e.g., monoidal models of computation [4]), and by laxified/“skew” monoidal structures where associativity or unit constraints may be non-invertible [5], we consider a setting in which irreversibility is encoded as a distortion operator: a non-invertible endomorphism that models information loss or coarse-graining along a computation. The question we address is: Can a lower-bound strategy that is invariant under irreversible distortions avoid known barriers and prove strong circuit lower bounds? We answer negatively for a large class of strategies by defining a DMT-analogue of natural properties and proving a barrier theorem via reduction to [1]. Informal summary of results. We define DMT-natural properties as those that are (1) decidable efficiently given a truth table (constructive), (2) satisfied by a non-negligible fraction of Boolean functions (large), and (3) stable under an abstract distortion operator (distortion-invariant). We then show that any such property induces a standard natural property in the sense of Razborov– Rudich, and thus is subject to the Natural Proofs barrier under standard assumptions. 1 2 Preliminaries: circuits and natural properties Fix n∈N. A Boolean function is a map f:{0,1}n→ {0,1}. We write Fnfor the set of all n-input Boolean functions; note |Fn|= 22n. A (nonuniform) Boolean circuit family of size s(n) computes fif for each nthere is a circuit Cnof size at most s(n) computing fon {0,1}n. Definition 1 (Circuit class P/poly).A Boolean function f:{0,1}n→ {0,1}is in P/poly if there exists a polynomial psuch that fis computed by a family of circuits of size at most p(n). Definition 2 (Razborov–Rudich natural property [1]).Let P= (Pn)n≥1be a sequence where Pn⊆ Fn. We say Pis natural (with parameters) if: 1. Constructive: there is a deterministic algorithm that, on input the truth table of f∈ Fn(of length 2n), decides whether f∈ Pnin time poly(2n). 2. Large: there exists a constant c > 0 such that for all sufficiently large n, Prf←Fn[f∈ Pn]≥2−cn. We say Pis useful against a circuit size bound s(n) if for all sufficiently large n, every f∈ Pnhas circuit size strictly larger than s(n). Razborov and Rudich prove that, under the existence of sufficiently hard pseudorandom functions, no natural property can be useful against P/poly-size circuits. Theorem 1 (Natural Proofs barrier, informal form [1]).Assume there exist pseudorandom functions with exponential hardness against polynomial-size circuits. Then there is no natural property useful against P/poly. In particular, no method that can be formalized as such a natural property can prove superpolynomial lower bounds for general circuits. Remark 1. For full parameterization (hardness exponent, circuit size bounds, and the precise quantitative trade-offs), see [1]. Our results below require only that a Razborov–Rudich-style barrier applies to the induced natural property. 3 A minimal DMT formalization We now introduce a deliberately lightweight abstraction capturing the aspects needed for a barrier theorem. The goal is not to propose a complete categorical theory of complexity, but to specify what it means for a lower-bound method to be (a) compositional/monoidal and (b) invariant under an abstract irreversible distortion. 3.1 Distorted monoidal models Definition 3 (DMT structure).Adistorted monoidal structure for Boolean functions consists of: 1. For each n, a representation map repn:Fn→Mn, where Mnis a set of “morphisms of arity n” (abstract syntactic objects). 2. For each n, a distortion operator δn:Mn→Mn. 3. A notion of semantic evaluation [[·]]n:Mn→ Fnsuch that [[repn(f)]]n=ffor all f∈ Fn. We require only the following axioms: 1. Soundness of distortion: for all m∈Mn, the function [[δn(m)]]nis a well-defined element of Fn. 2 2. Truth-table accessibility: there is a deterministic algorithm that, given the truth table of f∈ Fn, computes a description of repn(f) and, given a description of m∈Mn, computes the truth table of [[m]]nin time poly(2n). Remark 2. In richer categorical settings, one may take Mnto be hom-sets of a (possibly skew) monoidal category and δto be a non-invertible (lax monoidal) endofunctor capturing coarsegraining or irreversibility (cf. skew monoidal structures [5] and monoidal computational semantics [4]). For the barrier theorem, the minimal interface above suffices. 3.2 DMT-natural properties Definition 4 (DMT-invariant property).A sequence Q= (Qn)n≥1with Qn⊆ Fnis distortioninvariant (with respect to a fixed DMT structure) if for all nand all f∈ Fn, f∈ Qn⇐⇒ [[δn(repn(f))]]n∈ Qn. Definition 5 (DMT-natural property).A property sequence Q= (Qn)n≥1is DMT-natural if: 1. DMT-constructive: given the truth table of f∈ Fn, membership f∈ Qnis decidable in time poly(2n); 2. DMT-large: there exists c > 0 such that for all sufficiently large n, Prf←Fn[f∈ Qn]≥2−cn; 3. Distortion-invariant: Qis distortion-invariant. We say Qis useful against size s(n) circuits if no f∈ Qnhas circuits of size at most s(n) for all sufficiently large n. Remark 3. The “DMT” content is the extra invariance constraint. Intuitively, a DMT-natural method is a lower-bound criterion that (i) is efficiently checkable from a truth table, (ii) holds for a non-negligible fraction of functions, and (iii) cannot distinguish a function from its distorted (irreversibly coarse-grained) form. The barrier theorem below states that such strategies remain subject to the Natural Proofs obstruction. 4 Main result: a distorted-monoidal barrier theorem We now state and prove the main theorem. The proof is a clean reduction: DMT-natural properties are, in particular, natural properties in the classical sense. Therefore the Razborov–Rudich barrier applies immediately under the same pseudorandomness assumptions. Lemma 1 (DMT-natural implies natural).Let Qbe a DMT-natural property sequence. Then Q is a natural property sequence in the sense of Razborov–Rudich. Moreover, if Qis useful against a circuit size bound s(n), it is useful against s(n)in the classical sense. Proof. By definition, DMT-constructive means that given the truth table of f∈ Fnwe can decide f∈ Qnin time poly(2n), which is exactly the constructivity requirement for a natural property. Similarly, DMT-large is identical to the largeness condition. Finally, “useful against s(n)” is stated purely in terms of circuit sizes of the underlying Boolean functions and thus coincides with the standard definition. The distortion-invariance requirement is an additional constraint and does not weaken these implications. Therefore, Qis a (classical) natural property, and usefulness transfers unchanged. 3 Theorem 2 (Distorted-monoidal barrier theorem).Assume the pseudorandomness hardness hypothesis required by the Razborov–Rudich Natural Proofs barrier theorem holds (e.g., the existence of pseudorandom functions with exponential hardness against polynomial-size circuits, as in [1]). Then there is no DMT-natural property useful against P/poly. Consequently, any lower-bound approach that can be expressed as a DMT-natural property cannot yield superpolynomial circuit lower bounds for general circuits, and in particular cannot separate Pfrom NP by such a method. Proof. Suppose for contradiction that there exists a DMT-natural property Quseful against P/poly. By Lemma 1,Qis a (classical) natural property useful against P/poly. This contradicts the Natural Proofs barrier under the stated pseudorandomness hypothesis (Theorem 1, cf. [1]). Therefore no such DMT-natural property exists. Corollary 1 (No distortion-invariant “natural” separation strategy).Under the same pseudorandomness hypothesis, any proof strategy for superpolynomial lower bounds that (when formalized) yields a DMT-natural property must fail. Proof. Immediate from Theorem 2. 5 Discussion 5.1 What the theorem does and does not say Theorem 2is a barrier theorem: it explains why an entire class of techniques cannot succeed (assuming standard cryptographic hardness). It does not prove P = NP, nor does it rule out all possible circuit lower-bound methods. The novelty in the DMT packaging is the interpretation: the obstruction persists even if one insists that a method be invariant under a non-invertible distortion operator intended to model irreversibility or coarse-graining of computations. In other words, “extracting an invariant from irreversible distortion” does not by itself evade the Natural Proofs barrier, so long as the method remains constructive and large. 5.2 Relation to “almost-natural” and other refinements Chow introduced almost-natural proofs which relax largeness in a controlled way while retaining constructivity and some form of usefulness, exploring the boundary of the Razborov–Rudich obstruction [2]. Williams studied connections between natural proofs and derandomization, showing that certain weakenings can be powerful and relating the barrier to other complexity hypotheses [3]. The DMT-natural notion can be varied analogously: for example, one may weaken largeness to a smaller density, or restrict constructivity, or change the distortion-invariance condition. Such variants may fall outside the scope of Theorem 2and could be investigated separately. 5.3 Categorical semantics perspective The minimal DMT definition used here deliberately avoids committing to specific categorical machinery. Nevertheless, it is compatible with the general viewpoint that monoidal (and sometimes skew monoidal) structures provide compositional languages for computation and resources [4,5]. A more ambitious development would define Mnas morphisms in a (skew) monoidal category, interpret δas a lax monoidal endofunctor, and study which proof principles correspond to naturalness, 4 largeness, or constructivity. Our result indicates that as long as the induced property meets the classical naturalness criteria, the same barrier applies. 6 Conclusion We provided a precise DMT-flavored formalization of “distortion-invariant” lower-bound strategies and proved a barrier theorem: under standard pseudorandomness hardness assumptions, no DMTnatural property can be useful against P/poly. The proof is a reduction to the Razborov–Rudich Natural Proofs barrier. This supplies a structural explanation—within an irreversibility-aware, compositional vocabulary—for why a broad family of seemingly robust strategies cannot resolve P vs. NP. References [1] Alexander A. Razborov and Steven Rudich. Natural Proofs. Journal of Computer and System Sciences, 55(1):24–35, 1997. DOI: 10.1006/jcss.1997.1494. [2] Timothy Y. Chow. Almost-natural proofs. Journal of Computer and System Sciences, 77(4):728–737, 2011. DOI: 10.1016/j.jcss.2010.06.017. [3] R. Ryan Williams. Natural Proofs versus Derandomization. SIAM Journal on Computing, 45(2):497–529, 2016. DOI: 10.1137/130938219. [4] Duˇsko Pavlovi´c. Monoidal computer I: Basic computability by string diagrams. Information and Computation, 226:94–116, 2013. DOI: 10.1016/j.ic.2013.02.003. [5] Stephen Lack and Ross Street. Skew monoidales, skew warpings and quantum categories. Theory and Applications of Categories, 26(15):385–402, 2012. Available: arXiv:1205.0074. 5