Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata

Guy Bresler, Chenghao Guo, Yury Polyanskiy

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.

Evolution of the feasible region in a Polynomial Linear Program as the parameter $\delta$ varies.

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

Abstract

Given a matrix $A$ and vector $b$ with polynomial entries in $d$ real variables $δ=(δ_1,\ldots,δ_d)$ we consider the following notion of feasibility: the pair $(A,b)$ is locally feasible if there exists an open neighborhood $U$ of $0$ such that for every $δ\in U$ there exists $x$ satisfying $A(δ)x\ge b(δ)$ entry-wise. For $d=1$ we construct a polynomial time algorithm for deciding local feasibility. For $d \ge 2$ we show local feasibility is NP-hard. This also gives the first polynomial-time algorithm for the asymptotic linear program problem introduced by Jeroslow in 1973. As an application (which was the primary motivation for this work) we give a computer-assisted proof of ergodicity of the following elementary 1D cellular automaton: given the current state $η_t \in \{0,1\}^{\mathbb{Z}}$ the next state $η_{t+1}(n)$ at each vertex $n\in \mathbb{Z}$ is obtained by $η_{t+1}(n)= \text{NAND}\big(\text{BSC}_δ(η_t(n-1)), \text{BSC}_δ(η_t(n))\big)$. Here the binary symmetric channel $\text{BSC}_δ$ takes a bit as input and flips it with probability $δ$ (and leaves it unchanged with probability $1-δ$). It is shown that there exists $δ_0>0$ such that for all $0<δ<δ_0$ the distribution of $η_t$ converges to a unique stationary measure irrespective of the initial condition $η_0$. We also consider the problem of broadcasting information on the 2D-grid of noisy binary-symmetric channels $\text{BSC}_δ$, where each node may apply an arbitrary processing function to its input bits. We prove that there exists $δ_0'>0$ such that for all noise levels $0<δ<δ_0'$ it is impossible to broadcast information for any processing function, as conjectured by Makur, Mossel and Polyanskiy.
BibTeX
@misc{bresler2022linear,
  author = {Guy Bresler and Chenghao Guo and Yury Polyanskiy},
  title = {{Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata}},
  year = {2022},
  eprint = {2204.06357},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2204.06357},
}

Loading related content...

Figure