💻 computer science

Syntactic Separation Implies Computational Indistinguishability: An Abstract Obstruction Theorem

This paper establishes that syntactic separation within a local system implies computational indistinguishability, proving new derivation-length lower bounds for Skolem function equivalence and demonstrating how this obstruction unifies fundamental barriers in complexity theory, logic, and cryptography.

Original authors: Fabio F. G. Buono

Published 2026-06-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Fabio F. G. Buono

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: The "Blindfolded Mechanic"

Imagine you have a very smart, but strictly local robot mechanic. This robot can only look at a machine part and the tiny bits immediately touching it (say, within a 1-inch radius). It cannot see the whole engine, nor can it peek inside a sealed box.

This paper proves a surprising rule about what this robot can and cannot do: If two things are hidden inside separate sealed boxes that the robot can't open, the robot will never be able to prove those two things are actually the same, even if they are.

Furthermore, if you try to build a bigger, smarter robot that can figure this out, the paper proves it will take an astronomically long time (so long that it's practically impossible) to do so, simply because the information is hidden in a way that the robot's "local vision" can't bridge.

The Three Main Characters

To understand the paper, we need to meet three characters that appear in different fields (math, code, and logic):

The Local Robot (The Syntactic System): This is a set of rules that only looks at the "shape" of things right in front of it. It doesn't care about what things mean (semantics), only what they look like (syntax).
The Sealed Boxes (Protected Positions): These are parts of the machine (or code) that the robot is forbidden to touch or look inside. The robot's rules simply don't apply there.
The Secret Twins (Skolem Functions): Imagine two identical twins, Alice and Bob. In the real world (the "model"), they are the exact same person. But in the robot's world, Alice is locked in Box A and Bob is locked in Box B. The robot can see the boxes, but it can't see inside them.

The Two Big Discoveries

The paper presents a "Two-Case Theorem" that applies to all these scenarios.

Case 1: The Impossible Task

The Claim: If the robot is strictly local and the twins are in separate, sealed boxes, the robot can never prove that Alice and Bob are the same person.
The Analogy: Imagine you have a puzzle where two pieces look different because they are wrapped in different colored paper. The robot is only allowed to look at the paper wrapping. It can never see the pieces inside. No matter how many times it rearranges the outside paper, it can never conclude, "Ah, the pieces inside are identical!" because it can never touch the pieces.
Why it matters: This explains why certain mathematical proofs fail. If the "proof" relies on looking inside a sealed box, and the rules of the system forbid looking inside, the proof is impossible.

Case 2: The Expensive Escape

The Claim: If you try to upgrade the robot to make it smart enough to solve this, you have to pay a huge price. The paper proves that to prove the twins are the same, the robot would need to take a number of steps that grows exponentially (like $2^n$ ).
The Analogy: Imagine you have 100 different locked boxes. To prove the contents are the same, you might think you just need to check a few. But the paper says: "No, you have to check every single combination of boxes." If you have 10 boxes, you might need 1,000 steps. If you have 20 boxes, you might need over a million steps. If you have 100 boxes, the number of steps is so huge it exceeds the number of atoms in the universe.
Why it matters: This explains why some computer problems are "hard." It's not just that the math is hard; it's that the information is structurally hidden so well that any local attempt to find it requires an impossible amount of work.

Connecting the Dots: One Rule, Many Worlds

The most exciting part of this paper is that it shows this "Blindfolded Mechanic" problem isn't just one thing; it's the same problem showing up in four different fields of science:

Math (Proof Theory):
- The Problem: Trying to prove two different mathematical proofs lead to the same result.
- The Result: If the proofs use "secret constants" (like our twins) that the proof rules can't touch, you can't prove they are equal.
Cryptography (Secret Codes):
- The Problem: Hiding a secret message.
- The Result: The paper says that a "local" attacker (someone who can only look at small parts of the code) cannot tell the difference between two encrypted messages. The "cost" to break the code is the same exponential explosion of steps we saw in Case 2. The "impossibility" of Case 1 is exactly what makes a code "perfectly secure."
Type Theory (Computer Programming):
- The Problem: Checking if two computer programs do the exact same thing.
- The Result: A computer program checker can only look at the code's shape. It cannot see what the code actually does (the meaning). If two programs do the same thing but look different, the checker can never prove they are equal. It's "blind" to the function's true behavior.
Circuit Complexity (Chip Design):
- The Problem: Proving that a computer chip is too complex to be built efficiently.
- The Result: There is a famous barrier called "Natural Proofs" that says we can't prove certain chips are hard to build. This paper explains why: The "hardness" of the chip is a property of the whole function, but our tools only look at small parts of the chip. We are structurally blind to the complexity.

The "Aha!" Moment

The paper's main conclusion is that hiding is a structural feature, not just a computational one.

Think of it like a game of "Whac-A-Mole."

The Mole: The secret truth (that the twins are the same, or that the code is secure).
The Hammer: The rules of the system (the robot's local vision).
The Result: The hammer can only hit the surface. The mole is hiding deep underground. No matter how fast you swing the hammer (how many steps you take), you can't hit the mole unless you swing it a number of times that is exponentially larger than the size of the game board.

Summary

This paper doesn't invent a new way to break codes or solve math problems. Instead, it draws a map showing that proof theory, cryptography, and computer science are all fighting the same invisible wall.

The wall is built from local rules that cannot see global truths.

If you stay on the local side, you can never prove the global truth (Case 1).
If you try to jump the wall, you have to climb a mountain that gets exponentially higher the more you try (Case 2).

This explains why some things in math and computing feel impossible: it's not that we aren't smart enough; it's that the rules of the game are designed to keep the answer hidden from our local view.

Technical Summary: Syntactic Separation Implies Computational Indistinguishability

Problem Statement

The paper addresses a fundamental conflict between local syntactic systems and global semantic properties. In various domains—proof theory, cryptography, type theory, and circuit complexity—systems operate by inspecting the local structure of expressions (terms, truth tables, or proof terms) without access to their global semantic meaning. The central problem is to formalize why certain semantic invariants (such as the equality of two Skolem functions, the extensional equality of proof terms, or the circuit complexity of a function) remain inaccessible to these local systems, even when the system performs a sequence of valid derivations.

Specifically, the paper investigates:

Impossibility: Under what conditions can a local syntactic system never derive the equivalence of two semantically equivalent terms?
Complexity: If the system is extended to overcome this barrier, what is the minimum computational cost (derivation length) required to do so?

Methodology

The author introduces an abstract framework based on Local Syntactic Systems and Observational Blindness.

Core Definitions

Local Syntactic System ( $R$ ): A tuple $(\Sigma, V, \text{Rules}, r_0)$ where rules rewrite terms based only on a "context of radius $r_0$ " around the application position. The system is model-independent; rule applicability depends solely on syntactic form, not semantic truth.
Protected Positions ( $F$ ): A set of positions in a term structure where no rule is applicable, and no rule can rewrite inside the subterm. This is verified by checking for "first-symbol clashes" or structural mismatches between rule left-hand sides and the protected terms.
Syntactic Invariant ( $\text{Inv}$ ): A property of terms anchored to $F$ that is locally checkable, holds initially, is preserved by all rules, and whose violation requires acting on protected positions.
Syntactic Separation: Two Skolem functions $f$ and $g$ are syntactically separated if their occurrences in the initial clause set lie in disjoint protected sets $F_f$ and $F_g$ .

Theoretical Approach

The paper formalizes the system as a constrained observer ( $O_R$ ) that maps terms to their local contexts. The main argument relies on the fact that if a semantic invariant is "protected" (encoded in positions invisible to the observer), the observer cannot distinguish between configurations that differ only in the hidden semantic data.

The proof structure proceeds in two cases:

Case 1 (Impossibility): Using induction on derivation length and the preservation of the syntactic invariant, the paper proves that no derivation can produce a clause equating two syntactically separated Skolem functions.
Case 2 (Lower Bound): The paper constructs a family of "gadget instances" $\{I_n\}$ containing $2^n$ global configurations that are locally indistinguishable within radius $r_0$ . It demonstrates that any sound local extension $R'$ capable of distinguishing these configurations (and thus proving the equivalence) must perform a number of rule applications proportional to the number of independent gadgets, yielding a lower bound of $\Omega(n)$ , or $\Omega(2^n)$ under specific clause-per-configuration encodings.

Key Contributions

1. Abstract Obstruction Theorem (Theorem 3.1)

The paper establishes a two-case theorem parametric in the signature, locality radius, and model:

Case 1: If two Skolem functions are syntactically separated, no derivation in the base system $R$ can prove their equivalence.
Case 2: Any sound local extension $R'$ requires $\Omega(n)$ steps to prove equivalence on a family of $n$ independent gadgets. Under a specific encoding, this improves to $\Omega(2^n)$ .

2. Cryptographic Correspondence

The paper provides a formal dictionary mapping proof-theoretic concepts to cryptographic ones:

Protected Positions $\leftrightarrow$ Commitment schemes (hiding the opening).
Syntactic Separation $\leftrightarrow$ Ciphertext indistinguishability.
Derivation Cost $\leftrightarrow$ Adversary's advantage (negligible for polynomial-time adversaries).
Result: The lower bound on derivation steps is structurally identical to the requirement for an adversary to break a computational hiding scheme.

3. Cross-Domain Unification

The paper demonstrates that the following established results are specific instances of the same abstract obstruction:

Proof Theory: The incomparability of Open Induction (OI) and Clause Set Cycles (TCSC) regarding the commutativity of addition.
Type Theory: The Type Omitting Theorem and the inability of constructive type systems to decide extensional equality of proof terms.
Circuit Complexity: The Natural Proofs barrier of Razborov and Rudich. The paper argues this barrier is not merely a consequence of computational hardness (pseudo-randomness) but of observational blindness.

Results

Unconditional Lower Bounds

A primary result is the derivation of unconditional lower bounds that do not rely on unproven complexity assumptions (like $P \neq NP$ or the existence of secure Pseudo-Random Generators).

For any local syntactic system attempting to decide circuit complexity on $n$ independent witnesses, an inspection cost of $\Omega(n)$ is required.
This holds even in "Algorithmica" (where $P=NP$), because the barrier arises from the structural inability of the local observer to see the semantic invariant, not from computational difficulty.

Quantitative Bounds

Case 1: Strict impossibility of deriving equivalence for syntactically separated functions.
Case 2: Derivation length $L \geq \Omega(n)$ for $n$ independent gadgets. If the instance size is encoded to have one clause per configuration ( $|I_n| = 2^n$ ), the bound tightens to $L \geq \Omega(2^n)$ .

Specific Instantiations

Superposition Calculus: Re-proves that TCSC cannot prove the commutativity of addition ( $OI \not\subseteq TCSC$ ) because Skolem constants for the witnesses are protected by first-symbol clashes.
Natural Proofs: Shows that the Razborov-Rudich barrier is a consequence of the fact that large, constructive properties are local observers that cannot see the circuit complexity (a global semantic invariant). The PRG assumption is only needed to generate the $2^n$ indistinguishable instances, not to prove the structural blindness itself.

Significance and Claims

The paper claims to unify disparate impossibility results and lower bounds under a single structural principle: Observational Blindness.

Structural vs. Computational: The paper argues that barriers in complexity and logic are often "observational" rather than "computational." A system fails not because the problem is hard to compute, but because the system's local rules cannot "see" the relevant semantic invariant. This explains why such barriers persist regardless of the computational world (e.g., even if $P=NP$).
Unification of Domains: By treating proof theory, cryptography, type theory, and circuit complexity as instances of the same abstract theorem, the paper provides a unified explanation for why certain properties (extensional equality, circuit complexity, Skolem equivalence) are inaccessible to local syntactic inspection.
New Lower Bounds: The paper claims the derivation-length lower bound ( $\Omega(n)$ and $\Omega(2^n)$ ) is new to the literature on Skolemization and saturation proving. It also claims to provide the first unconditional lower bound on the inspection cost of natural proofs that does not rely on PRG assumptions.
Cryptographic Reading: The paper asserts that the proof-theoretic structure of Case 2 is precisely the structure of computational hiding. The cost of deriving a proof is the "negligible advantage" of an adversary, and the syntactic separation is the "indistinguishability" of ciphertexts.

The paper concludes that these barriers are not artifacts of specific systems but are inherent to any system that acts locally on a representation while the semantic invariant is encoded globally. The result of Loff et al. [14] is cited as a quantitative confirmation of this framework for $AC^0$ -natural proofs.