Wythoff Nim完全値の計算量

Trigger

Wythoff Nim の特殊な色、特に G(n,m)=1 の判定ではなく、完全な Sprague--Grundy 値
G(n,m) を計算する時間計算量を上下から完全に決定したい。入力長を
L=Theta(log n+log m) と見る単一問と、0<=n,m<=N の完全表を作る問題を区別する。

Goal

完全表について既知の素朴な cubic 計算を破り、最終的には単一問を入力桁数の多項式時間で
計算できるか、またはそのような算法が不可能であることを意味のある計算モデルで示す。
Wythoff の三方向を A2 正根系、Hall algebra、affine symmetric group と結び、単なる類似でなく
mex の計算を実際に圧縮する構造を探す。

Current frontier

• 三本の合法手を A2 の正根方向として、Boolean Hall support から厳密に復元できる。
• 完全表には word-RAM で O(N^3/log N) の厳密な word-parallel 算法がある。ただし bit 計算量は
  まだ cubic であり、この評価の文献上の新規性も未確定である。
• 各固定行は有限個の例外を除いて affine symmetric group の元になる。
• 自然な Zeckendorf prefix、有限個の先頭hole、隣接行の短い Coxeter 更新は高速化に使えない。

Next theorem target

色 h と行 r に対する三つの禁止集合 D_h, B_h-r, L_r の和集合が dyadic interval を
完全に覆うかを、polylogarithmic size の affine cut-set で判定する。これができれば、最初の
非被覆点を区間二分で求め、完全表を O(N^2 polylog N) で計算できる可能性がある。