2025年10月27日¶
\(\newcommand{Cone}{\mathop{\operatorname{cone}}}\) \(\newcommand{Span}{\mathop{\operatorname{span}}}\) \(\newcommand{Supp}{\mathop{\operatorname{supp}}}\) \(\newcommand{BSeq}{\mathop{\operatorname{Seq'}}}\) \(\newcommand{Intr}{\mathop{\operatorname{int}}}\)
3-VAS is PSPACE-complete¶
(construction by Sławomir)
We reduce from bounded 1-VASS. Recall in Hopcroft-Pansoit we encode state \(p \in [n]\) as \((p, n(n+1)(n-p), 0)\). Transitions then use the counter with \(0\) to determine which phase of state transition we are in.
For bounded 1-VASS with bound \(B\), we just simulate \(p(x)\) by something like \((p \times B + x, A \times B \times (n - p) + B - x, 0)\), where \(A\) is a very big number.
(not fully checked)