The Core Intuition: Unary vs. Binary Input Lengths
In theoretical computer science, the computational complexity of a problem is always measured relative to the length of its input string. This dependency introduces a profound and often counterintuitive vulnerability when problems involve numbers: the choice of numerical encoding can completely alter a problem's complexity class.
To see why, consider passing a large integer $N$ (say, one million) to an algorithm.
- If you encode $N$ in unary (as a sequence of $N$ ones:
111...1), the length of your input string is exactly $1,000,000$. An algorithm that takes $O(N)$ operations runs in linear time relative to the input size. - If you encode $N$ in binary (as
11110100001001000000), the length of your input string shrinks exponentially to just $\lfloor\log_2 N\rfloor + 1 = 20$ characters. Now, that same $O(N)$ algorithm requires $O(2^{|input|})$ operations—meaning it scales exponentially relative to the input size.
This phenomenon is known as numerical encoding sensitivity. When a problem is solvable in polynomial time using unary encoding but becomes NP-hard (or worse) under binary encoding, it is said to have pseudo-polynomial complexity. However, recent research across logic, automata theory, and optimization reveals that this sensitivity goes far beyond simple runtime slowdowns. Binary encoding acts as a powerful compression mechanism, allowing a tiny input string to implicitly describe an exponentially vast mathematical structure, often forcing the underlying problem into a fundamentally higher complexity class.
The Succinctness Trap and State-Space Explosion
When an input parameter is encoded in binary, it allows a user to specify astronomical bounds or constraints using very few bits. This compact representation frequently triggers a massive state-space explosion during verification or planning tasks.
For example, in automated planning, a system might search for a sequence of actions within a specific length bound. As shown by Songtuan Lin et al., changing this step limit from a unary representation to a binary representation elevates the complexity of verifying plan existence from NP-complete to NEXPTIME-complete. Because binary encoding allows exponentially larger bounds to be written in a compact format, the search space of potential plans expands exponentially relative to the description length.
A parallel effect occurs in the verification of modern machine learning architectures. In The Computational Complexity of Satisfiability in State Space Models, the authors demonstrate that verifying properties of State Space Models (such as Mamba or S4) shifts from NP-complete to NEXPTIME when sequence length constraints are switched from unary to binary. The succinct binary bound forces the verification algorithm to navigate an exponentially larger unrolled computational graph.
Similarly, in probabilistic graphical models, the way domain sizes are specified dictates scaling behavior. Fabio Cozman et al. showed that representing the number of individuals in a relational Bayesian network using binary notation causes the grounded network to grow exponentially, driving the complexity up to #EXP-hard.
Shifting Borders in Automata and Counter Systems
In automata theory, Vector Addition Systems with States (VASS) and counter nets are used to model concurrent systems by tracking integer counters. The complexity of determining whether a specific system state is reachable depends heavily on how counter updates are encoded.
Unary Encoding: [+1, +1, +1, +1] --> Path length scales linearly with input
Binary Encoding: [+4] --> Path length can scale exponentially with input
For two-dimensional VASS, Matthias Englert et al. settled a long-standing question by proving that reachability under unary encoding is NL-complete, placing it in the same class as standard graph reachability. This works because unary encoding guarantees that any reachability witness (path) is of pseudo-polynomial length.
When counter updates are represented succinctly in binary, the problem becomes PSPACE-complete. As noted by Shaull Almagor et al. in their analysis of two-way one-counter nets, binary updates invalidate classical proofs that rely on polynomial-length runs. The succinct updates allow the system to execute exponentially long sequences of operations before triggering a counter boundary, requiring entirely new theoretical frameworks to establish tractability bounds, a challenge also explored by Diego Figueira et al. for branching VASS.
Logic and Knowledge Representation: When Binary is Free
Intuitively, one might expect that switching from unary to binary encoding always increases worst-case complexity. However, description logics and modal calculi reveal a surprising counter-pattern: some logical frameworks are entirely robust against encoding changes.
In description logics, numerical constraints appear as qualified number restrictions (e.g., asserting that a concept must have at least $N$ distinct successors). In The Complexity of Finite Model Reasoning in Description Logics, the authors proved that reasoning about finite models in the logic $\mathcal{ALCQI}$ remains EXPTIME-complete regardless of whether numbers are represented unarily or binarily.
How do they achieve this robustness? The authors utilize a reduction that simulates binary-coded numbers through chains of auxiliary roles and concepts, effectively bypassing the state-space explosion. As further detailed by Carsten Lutz et al., large numerical constraints can be reduced to simpler logical structures restricted to zero or one without incurring an exponential blow-up. This same resilience appears in modal logic; Aniello Murano et al. demonstrated that satisfiability for the $\mu$-calculus with graded modalities remains EXPTIME-complete under binary coding, ensuring that compact formula sizes do not penalize the decision procedure.
Robust Logics (e.g., ALCQI):
Binary Constraints ──[Auxiliary Chains]──> Simulated Base-1 Structures (No Complexity Jump)
Fragile Logics (e.g., Transitive Roles):
Binary Constraints ──[Grid Simulation]───> Exponentially Large Torus (EXPTIME -> NEXPTIME)
However, this robustness breaks down when the logic allows interactions between counting and structure. Víctor Gutiérrez-Basulto et al. showed that when number restrictions are placed on transitive roles alongside nominals, the complexity jumps from EXPTIME to NEXPTIME. Here, the compact binary numbers allow the logic to efficiently enforce and verify massive, highly regular grid or torus structures that cannot be constructed when numbers are constrained to a unary range.
Structural Taming in Optimization and Decision Problems
In discrete optimization, such as Integer Linear Programming (ILP) and resource-constrained scheduling, binary-encoded coefficients typically preserve NP-hardness. This creates a significant gap between theoretical tractability and practical implementation.
To bridge this gap, researchers look for structural parameters that can "tame" the numerical complexity. In Solving Integer Linear Programs with a Small Number of Global Variables and Constraints, the authors introduce fracture backdoors. They demonstrate that while large binary coefficients maintain problem hardness, restricting coefficients to a unary range allows ILP to become fixed-parameter tractable (FPT) when structural complexity is low. Similarly, Eduard Eiben et al. leverage unary encoding bounds alongside graph parameters like signed clique-width to map out new islands of tractability for ILP.
When structural parameters are absent, the encoding choice dictates whether a problem can be solved efficiently. In The Complexity Landscape of Resource-Constrained Scheduling, the authors show that many scheduling variants that appear tractable under unary encoding remain strictly NP-hard in the general binary case, because binary task durations allow for exponential scheduling horizons.
This boundary remains one of the most active frontiers in complexity theory. For instance, Paul W. Goldberg proved that the Discrete Ham Sandwich problem is PPA-complete when coordinates are represented in binary, but whether this hardness persists under unary encoding remains an open question. As algorithms advance, decoupling structural graph properties from numerical encoding constraints—as pursued by Alexandra Anna Lassota et al.—remains essential for ensuring that theoretical tractability translates into real-world performance.
Key Foundational Work
The Complexity of Finite Model Reasoning in Description Logics (2002) — contributed 4 concept elements to this direction.
The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics (2000) — contributed 2 concept elements to this direction.
Using Auxiliary Variables and Implied Constraints to Model Non-Binary Problems (2000) — contributed 1 concept elements to this direction.