Local Optimality Does Not Compose: Invariant Simplices and the Complexity of Shared Probabilistic Automata
Abstract
Probabilistic models are often constructed separately for different test suites and then expected to share a single latent dynamical system. We study bounded-state shared realization for probabilistic automata from finite partial trace specifications. A shared realization uses one normalized automaton with named initial distributions, a common family of row-stochastic letter-transition matrices, and one final output vector. We compare it with separate local realizations and a labelled query-specific static relaxation. Local and labelled query-specific static optima need not compose. For every k,L≥1, we construct finite partial specifications for which each individual specification and the labelled query-specific static relaxation have minimum state count k, whereas every exact shared realization requires exactly k(L+1) states. The factor L+1 reflects the prefix progress that must be tracked by a single shared transition family. In the linear-rank-tight calibrated regime, the existence of an exact k-state shared realization is equivalent to finding a (k−1)-simplex containing the root responses, contained in the response polytope, and forward-invariant under every single-letter affine update. For finite rational specifications, exact shared realization with at most K states is ∃ℝ-complete, while distinguishing zero minimax defect from inverse-polynomial defect is PromiseNP-complete. Both classifications hold over a fixed five-letter alphabet when the local and labelled query-specific static optima already equal K. They remain valid with Boolean final output vectors, and the robust gap persists over the full cube [0,1]d. Thus the hardness arises from shared word composition.
Related
- Hankel Submatrices with Bounded Word Length: Dimension Tradeoffs in Probabilistic and Quantum Automata
- Fermionic quantum field theories as probabilistic cellular automata in three dimensions
- On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
- Isometry Groups of Right Invariant Metrics in Geometric Quantum Complexity
- Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
BibTeX
@misc{zhao2026local,
title = {{Local Optimality Does Not Compose: Invariant Simplices and the Complexity of Shared Probabilistic Automata}},
author = {Yixin Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.19707},
eprint = {2609.19707},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19707},
}
RIS
TY - UNPB
TI - Local Optimality Does Not Compose: Invariant Simplices and the Complexity of Shared Probabilistic Automata
AU - Yixin Zhao
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2609.19707
UR - https://arxiv.org/abs/2609.19707
AB - Probabilistic models are often constructed separately for different test suites and then expected to share a single latent dynamical system. We study bounded-state shared realization for probabilistic automata from finite partial trace specifications. A shared realization uses one normalized automaton with named initial distributions, a common family of row-stochastic letter-transition matrices, and one final output vector. We compare it with separate local realizations and a labelled query-specific static relaxation. Local and labelled query-specific static optima need not compose. For every k,L≥1, we construct finite partial specifications for which each individual specification and the labelled query-specific static relaxation have minimum state count k, whereas every exact shared realization requires exactly k(L+1) states. The factor L+1 reflects the prefix progress that must be tracked by a single shared transition family. In the linear-rank-tight calibrated regime, the existence of an exact k-state shared realization is equivalent to finding a (k−1)-simplex containing the root responses, contained in the response polytope, and forward-invariant under every single-letter affine update. For finite rational specifications, exact shared realization with at most K states is ∃ℝ-complete, while distinguishing zero minimax defect from inverse-polynomial defect is PromiseNP-complete. Both classifications hold over a fixed five-letter alphabet when the local and labelled query-specific static optima already equal K. They remain valid with Boolean final output vectors, and the robust gap persists over the full cube [0,1]^d. Thus the hardness arises from shared word composition.
ER -