Abstract
This research explores Polynomial Linear Programming (PLP), a specialized branch of optimization where linear constraints depend on a parameter $\delta$. The authors establish that checking the "local feasibility" of such systems—determining if a solution exists for all small $\delta$—is polynomial-time solvable for a single parameter but NP-hard for multiple parameters. These theoretical results are applied to resolve long-standing conjectures in the theory of computing and information physics, specifically regarding the ergodicity of 1D cellular automata and information broadcasting in noisy 2D grids.
Introduction: The Local Feasibility Problem
In standard Linear Programming (LP), the goal is to find a vector $x$ satisfying $Ax \ge b$ for fixed $A$ and $b$. However, many real-world systems are subject to external fluctuations such as noise or temperature. In these scenarios, the coefficients become functions of a parameter $\delta$.
The authors focus on Local Feasibility: determining if there exists a solution $x(\delta)$ for every value of $\delta$ in a small neighborhood around zero. Unlike robust optimization, which seeks a single $x$ for all noise levels, PLP allows the solution to evolve as $\delta$ changes. This framework is essential for proving the stability of systems like Probabilistic Cellular Automata (PCA), where researchers investigate whether a system eventually reaches a unique equilibrium (ergodicity) despite infinitesimal noise.
Algorithmic Methodology
The paper's contributions are divided between algorithmic theory and physical applications:
1. The 1-PLP Algorithm
For a single parameter $\delta$, the authors demonstrate that if a solution exists, a rational function solution $x(\delta)$ must also exist. They transform the feasibility problem into a "derivative condition," checking the signs of the polynomial coefficients at $\delta = 0$. This collapses an infinite search space into a finite, algebraic one by focusing on the first non-zero derivative at the origin.
2. Subspace Elimination
To handle the resulting logic problems involving complex disjunctions, the authors developed "Subspace Elimination." This polynomial-time algorithm checks if a union of affine subspaces covers the entire space, a critical step in verifying the feasibility of the derivative conditions.
3. Complexity and Hardness
While the 1-parameter case is tractable, the authors prove that the problem becomes NP-hard as soon as two or more parameters ($\delta_1, \delta_2$) are introduced. This result was achieved through a reduction from the Independent Set problem.
Applications in Information Physics
The authors utilized their 1-PLP solver to provide computer-assisted proofs for several open problems:
- Ergodicity of NAND PCA: The paper provides the first proof that the 1D NAND cellular automaton is ergodic under both vertex and edge noise for small noise levels. This was achieved by using the PLP solver to find "potential functions" (analogous to Lyapunov functions) that guarantee system stability.
- Broadcasting on 2D Grids: The research resolves a 2021 conjecture by proving that it is impossible to broadcast information indefinitely across a 2D grid of noisy NAND gates if the noise is small but non-zero.
Discussion and Future Work
While the algorithm provides a breakthrough in polynomial-time feasibility testing, its high computational complexity ($O(n^3 m D^3)$) currently limits its application to relatively simple rules. More complex systems, such as the "Soldier's Rule," remain computationally out of reach.
Furthermore, while the proofs hold for "sufficiently small" noise ($\delta < \delta_0$), the "monotonicity gap" remains: it is not yet formally proven that stability at low noise levels implies stability at higher noise levels. Future research will likely focus on identifying tractable subclasses of multi-parameter PLPs to extend these methods to more complex engineering and physical models.
Summary updated