Skip to content

2025年10月23日

\(\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}}}\)

Reachability in Sum-Geometric Dimension 3

One component case

  1. Remove rigid counters.
  2. In case of wide (see day 1) and pumpable (simply pumpable in every counter), we get easy path.
  3. Non-wideness immediately induces drop in geometric dimension.
  4. Non pumpable means one counter is bounded in the run. We encode this counter into states, the new cycle space will be orthogonal to this axis, thus dropping geometric dimension.

Remark

Notice that we don't really need the improved Rackoff lemma. (Even for 1-component case to get PSPACE bound?)

Many components case

Just be careful to show that the periods of approximations lies in the cycle space (actually cones) --- they are just combinations of cycles from SLPS.