# Syntactic Separation Implies Computational Indistinguishability: An Abstract Obstruction Theorem

arXiv: https://arxiv.org/abs/2606.29177 · HTML: https://mlsanity.com/paper/2606.29177/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2026.

## Built on by (most cited first, 1 of 1)

- [A Non-Formulable Theorem: A Fundamental Limit of Finite Syntactic Systems and Its Consequences for Security and AI](https://mlsanity.com/paper/2609.04086/) (2026)

## Abstract (arXiv)

We prove that syntactic separation implies computational indistinguishability. A local syntactic system R acts on terms within radius r0 without consulting any model; when two Skolem functions are syntactically separated in R, no derivation can prove their equivalence (Case 1), and any sound local extension requires Omega(n) steps, improving to Omega(2^n) under clause-per-configuration encoding (Case 2). Both bounds are new: the derivation-length lower bound does not appear in prior work on Skolemization or saturation proving, and the cryptographic reading, syntactic separation as ciphertext indistinguishability, derivation cost as negligible advantage, is original. The same obstruction, as formal instances of Case 1 and Case 2, governs the Natural Proofs barrier of Razborov and Rudich, the Type Omitting Theorem, and the unconditional AC^0 barrier of Loff et al. (2026).