正確な忘却と、
その後の選択肢
いまの意味を完全に保って情報を捨てたとき、将来の圧縮のしやすさはどこまで保たれるか。さらに、決まった保持数で将来の損失を最小にする残し方を、厳密に設計できるか。
今回、どこまで進んだか
第5版:追加査読に基づき、C1の前提を定理内に再掲し、C2の充填証明を補題化した。公平配分の近接研究を追加照合し、新規性の主張を限定。記号・六候補例の同率条件・再現手順・表の見出しも補正した。定理の値と達成例は維持した。
今回は、二資源の候補圧縮について「どれを、どの確率で残すのが最良か」まで解けた。現在の意味を全ての抽選結果で保ちながら、事前に固定された将来需要に対する期待損失を厳密に最小化できる。使用する区間抽出・双対性は既知で、C1・C2の導出も短い。貢献候補は、本モデルの厳密な保持数保証と反例を一体として整理した点に限定する。
前版の次元・一意性・需要削除数による分類と、②の忘却露呈の分析も以下に残した。いずれも数学的証明と先行研究上の新規性は別に評価する。
①の当初の問い「多資源の観測制約下での最小意味モデル」は広い。ここで解いたのは同じ制御状態で、既存の予算候補を削除する圧縮に限る。任意の意味モデル・任意の表現方式についての最小状態数問題は解いていない。
| 結果 | 数学的状態 | 新規性評価 |
|---|---|---|
| C1–C3:最適乱択保持 | 厳密値・有限分布・有理数算法・鋭い保持数曲線を証明。将来Eは抽選結果とは独立に固定。結果を見て選べる場合はB<gで最適保証2 | 既知の抽出法・区間双対性・公平配分と近接。貢献候補は本モデルの保証と反例の一体的整理に限定し、新規性は未確定 |
| A0:将来損失の局所代替公式 | 一般集合被覆で独立証明 | 劣加法性による基本補題。新原理とは主張しない |
| A1:Pareto 2Dで2倍 | 証明・鋭い例あり | 既知の左右最近傍置換の直接系 |
| A2:2Dで任意最小3倍/一意最小2倍、削除数hを含む次元別分類 | 上界と全条件での達成例を独立証明 | 同一の分類定理は確認資料内で未発見。新規性は未確定 |
| A3:2Dで初期余剰sならs+3倍 | 全s≥0で上界・達成例を証明 | 既知の交換論法の短い組合せである可能性を残す |
| B1:露呈長 Gk+1(n)−1 | 厳密値は維持。単項DFA帰着を明示 | 既知構造の鋭い系・独立導出。新発見の中心から外す |
「証明できた」と「世界で初めて」は別の判定である。今回の新規性調査は、読めた一次資料との比較まで。関連する旧論文・博士論文に本文未取得のものがあり、未発見を新規性の保証には使わない。
記号の適用範囲(第5版補足)
記号は節ごとに定義する。特にC2の区間数をN、必要総確率の関数をρ(λ)へ改め、同じ節でmとm(λ)が混在しないようにした。
| 記号 | 適用する節と意味 |
|---|---|
| B | C1–C3では保持数上限。到達可能性の還元ではSUBSET SUMの目標。断言更新では断言の共通部分。A2証明3では保持集合内の被覆集合。 |
| N、ρ(λ) | C2の異なる需要区間数、および保持確率の下限λに対する必要総確率の最小値。 |
| m | C3の達成構成ではg−q+2。3D無界例と最初の劣化の補論では、それぞれ局所的な構成の大きさ。これらは同じパラメータではない。 |
| L、L(P)、Lq | 露呈長の証明では巡回長の最小公倍数。劣化閾値の構成では座標の尺度m+1。C2のL(P)は選んだ区間長の総和。Lqは状態qの継続言語。A3の例には同名の候補Lもある。 |
| h | A2では削除需要数。一更新の全域関数では周期に入るまでの過渡長。 |
第4版の主結果:保持数から、最適な期待損失を求める
どの候補を消すかを確率的に選ぶと、現在の意味は毎回完全に保ちつつ、将来の最適個数の損失を小さくできる。二資源では、その最良の保証を厳密に計算し、保証を達成する抽選まで構成できた。前版の一律な損失上界から、保持方法を設計する算法へ進んだ点が、今回の中心である。
ここでの確率は保持方法の抽選にだけ入る。将来の需要 E は抽選の分布を知って選ばれてよいが、実際に選ばれた保持集合 T を見てから変更してはいけない。現在の需要を取りこぼす確率はゼロである。
まず、六候補で起こる改善
候補を ri=(i,7−i)、i=1,…,6 とする。現在の需要は (i,6−i)、i=1,…,5 に、両端の私有需要 r₁,r₆ を加えた七個。各需要は、隣り合う二候補、または端の一候補だけで処理できる。現在の意味を保つ最小保持数は4である。
| 保持上限 B | 固定した保持方法の最良の最悪比 | 抽選を許した最大期待比の最適値 |
|---|---|---|
| 4個 | 2 | 3/2 = 1.5 |
| 5個 | 2 | 5/4 = 1.25 |
| 6個 | 1 | 1 |
B=4 では {1,2,4,6} と {1,3,5,6} を確率1/2ずつで選ぶ。どちらも現在の全需要を覆う。両端は必ず残り、中の各候補は半分の確率で残る。どんな固定された将来需要でも、期待最適個数は未削除の場合の1.5倍以下となる。B=5 では中の四候補から捨てる一つを等確率で選ぶ。この例では両保証とも改善不能である。
保持数と、実際の抽選結果を切り替える
図の丸は一回の抽選結果、下の棒は抽選全体での保持確率。全ての結果を列挙した表示であり、少数回のシミュレーションによる推定ではない。
定義:最大化の順序を固定する
有限非空の需要 D と、それを覆う有限候補 R を二次元非負ベクトルとし、需要 z を候補 r が覆う条件を z≤r とする。S(r)={z∈D:z≤r}。τA(E) は候補 A から E を覆う最小個数、τA(∅)=0。各候補の保持費用は1とする。
許す分布 μ は、全ての抽選結果 T⊆R が D を覆い、|T|≤B を満たすもの。B は整数である。評価値を
とする。将来需要の確率分布は仮定しない。全ての固定された E に対する保証を、保持方法の抽選について期待値で測る。これは一回の圧縮の定理であり、適応的な削除・再抽選の反復保証ではない。
正規化:意味の異なる極大候補だけを残す
非空の担当集合 S(r) のうち、包含に関して極大な、異なるものごとに元候補を一つ選び、その代表集合を M とする。g=|M|、q=τR(D)=τM(D) と置く。全ての元候補は、自分の担当集合を含む極大代表へ置換できる。この置換は保持数も、任意の将来に必要な個数も増やさない。従って最適分布を M の部分集合に限定してよい。
代表同士は座標ごとには比較不能なので、第1座標の昇順に r₁,…,rg と並べると第2座標は降順になる。各需要 d を覆う添字は、空でない連続区間 Id⊆{1,…,g} となる。以下は q≤B≤g。B<q は実行不能、B≥g は全代表を保持して VB=1 である。
C1:最適乱択保持の厳密公式
前提。資源次元は d=2、有限非空需要 D は有限候補 R により座標ごとの支配で被覆される。候補費用は全て1。M={r₁,…,rg} は異なる非空極大担当集合ごとの代表に正規化済みで、第1座標の昇順に並ぶ。q=τR(D)、Bは整数、q≤B≤g とする。Id は需要dを覆う代表の添字区間。VB は、全実現でDを覆い高々B候補を保持する分布について、抽選結果とは独立に固定された将来Eへの最大期待比を最小化した値である。
次の線形計画の最適値を λ* とする。xi は代表 i の保持確率に相当する。式中の2は二次元の置換定数であり、一般の区間記法だけを根拠に三次元へ適用してはならない。
0≤λ≤1, λ≤xi≤1 (i=1,…,g),
Σixi≤B, Σi∈Idxi≥1 (d∈D).
VB = 2−λ*.
さらに、最適な x から、全ての抽選結果で現在の意味と保持数上限を守る有限分布を構成できる。独立なコインで各候補を残す方法は用いず、保持判断に相関を持たせる。
C1の証明:全将来の問題を、最小保持確率に還元する
まず任意の有限集合被覆について、期待値版のA0が成り立つ:
固定した E に対し、元の最小被覆 O を取る。各抽選結果で、O の各 r を S(r) の最小 T 被覆へ置換すれば、τT(E)≤Σr∈OτT(S(r))。期待値を取って |O| で割ると「≤」。逆向きには E=S(r) を選ぶ。この E の元の最適個数は1。空の担当集合は最大値に影響しない。包含の単調性から極大代表だけ調べればよい。
正規化された二次元では、既知の左右二候補による置換から τT(S(ri))≤2。極大担当集合が全て異なるので、一候補で覆えるのは ri 自身が残る場合だけ。従って
maxE 𝔼[τT(E)]/τR(E) = 2−miniPr(i∈T).
任意の実行可能分布の周辺確率はC1の制約を満たすため、VB≥2−λ*。逆向きは次の抽出法で示せる。□
実現する抽選:累積確率上の、ずらした整数格子
s₀=0、si=Σj≤ixj とし、θを [0,1) 上で一様に選ぶ。区間 (si−1,si] に θ+整数 が入るときにだけ候補 i を保持する。
各区間の長さは xi≤1 なので、保持確率は正確に xi。保持個数は高々 ⌈Σxi⌉≤B。需要区間 Id=[a,b] に対応する (sa−1,sb] は長さが1以上なので、どんな θ でもずらした整数を少なくとも一つ含む。従って需要は毎回覆われ、C1の等号が成立する。
累積和の小数部分で [0,1) を分割すると、各開区間上で保持集合が一定となる。高々 g+1 個の正の長さの区間の中点を選び、その長さを確率にすれば、同じ周辺確率の有限分布になる。必要なら Σxi=B まで余分な確率質量を加え、毎回ちょうど B 個を残すこともできる。
この抽出法は既知である。Elbassioni–Gajjala–Ray, arXiv:2607.28062v1(2026 07 30)、§3・式(2)・Claim 3.6に同じ累積和・シフトによる構成と区間被覆確率がある。本稿は新しい丸め法を主張しない。
C2:汎用LPなしで解ける、ボトルネック公式
互いに交わらない需要区間を k 個選んだときの、区間長の合計の最小値を ℓk とする。長さは候補の添字の個数で測り、ℓ₀=0。選べる最大の k は q である。
最小値を与える区間の組が、「これ以上よい保持確率にはできない」ことを説明する証明書になる。k=0 の項 B/g も含める。
ℓk は区間スケジューリングの動的計画法で求まる。次に xi=λ* から始め、右端の早い需要区間から順に、区間内の確率の和が1に足りない分を右側の添字から補う。これで最適な確率ベクトルが得られ、上の抽出法で実現できる。
添付ソルバーは整数と有理数だけを使い、この値と分布を厳密に計算する。明示された需要集合に対して多項式時間である。小さな遷移系が指数個の異なる継続費用を表す場合に、遷移系の記述長に関して多項式とは主張しない。
C2の証明と算法の詳細
λを固定し、xi=λ+yi と置く。必要な総確率の最小値 ρ(λ) は
である。ここで yi≤1−λ を省いてよい。超えた値を1−λへ切り下げても、各制約の右辺は1−λ以下なので制約を壊さない。
双対は、各添字を高々1回使う区間パッキングで、区間 I の重みは1−|I|λ。区間の連続1性から制約行列は完全単模であり、最適解を整数に取れる。従って、互いに交わらない区間族 P、その個数 k(P)、長さの合計 L(P) を用いて
空族も許す。λが実行可能なのは ρ(λ)≤B のときに限る。L(P)=g の場合は k(P)≤q≤B なので追加条件はない。それ以外は λ≤(B−k(P))/(g−L(P))。固定した k では分子が非負であり、比を最小化するのは L(P) が最小のとき。これで公式を得る。区間被覆とパッキングの双対性は既知で、Ben-David–Grant–Ma–Sharpe(CCCG 2012)、§1.2を参照。
異なる需要区間の個数を N とし、右端の昇順に並べる。p(j) を区間 j の左端より前に終わる最後の区間番号とする。最初の j 区間から k 個選ぶ最小合計長 F(j,k) は
F(j,0)=0, F(0,k>0)=∞, ℓk=F(N,k).
q を通常の区間貪欲法で先に求めれば、計算量は O(N log N+Nq)。配布実装は簡潔さのため k≤g まで走査するので O(N log N+Ng)。いずれも正規化と区間作成後の計算量である。
補題:右端優先充填は容量内で完了し、総量を最小にする
λ∈[0,1] を固定する。切り下げ論法により、λ≤zi≤1 の範囲で最小総量ρ(λ)を達成する完成解zが存在する。λ=λ* ならC2の公式からρ(λ*)≤Bである。貪欲法はxi=λから開始し、各区間を右端の昇順に処理する。
① 区間内の容量。現在の区間Iが不足し、Δ=1−Σi∈Ixi>0なら、その区間内の残容量は
Iは非空なので、右から容量1まで足せば必ず不足を埋められる。これは局所的な容量保証である。総量がBを超えないことは、次の最適完成解との不変条件から得る。
② 総量を保存する交換。「現在の貪欲ベクトルxを座標ごとに上回る、総量ρ(λ)の最適完成解zがある」を不変条件とする。区間I=[a,b]の添字tへ貪欲法が追加する途中で、ztが新しいxtに不足する場合を考える。右から充填するので、I内のtより右の添字は既にxj=1であり、zjに余剰はない。一方z(I)≥1で、今回の充填後のx(I)は高々1。従ってtより左の添字に、zがxを上回る十分な余剰がある。
その余剰を同じ量だけ添字tへ移す。移動先は新しいxt≤1までなので容量を守り、移動元は保護したxを下回らない。既処理区間は処理済みのxだけで被覆される。未処理区間は右端がb以上なので、左の移動元を含めば、その右にある移動先tも含む。現在の区間内でも総量は変わらない。従って全被覆制約を保ち、減らした量と増やした量が等しいためΣzi=ρ(λ)も不変である。
これを繰り返すと各充填後にもz≥xとなる。最終的に貪欲解x自身が実行可能となり、Σxi≤ρ(λ)。ρ(λ)の最小性から等号である。特にλ=λ*なら総量はρ(λ*)≤B。素朴な実装はO(Ng)。□
六候補例では (ℓ₀,…,ℓ₄)=(0,1,2,4,6)。B=4,5 とも k=2 が最適値を制約する(B=4ではk=3も同率で1/2)。両端の私有需要を満たすため2個分は必須で、中の四候補に均等に割り当てられる確率が (B−2)/4 となる。
C3:保持数と期待損失の、鋭い普遍曲線
g>q の全ての二次元インスタンスで、
任意の g>q≥2 と任意の B で、この上界を達成する例がある。これは g,q,B だけを知る場合の最良の一律保証。個々のインスタンスでは、C2によりさらによくなることがある。上の六候補例はその一つである。
C3の証明と、全パラメータでの達成例
正規化後の初期最小被覆 T₀(q個)を必ず保持し、それ以外の g−q 個から B−q 個を一様に選ぶ。追加候補の保持確率は p=(B−q)/(g−q) なのでC1の期待値恒等式から比2−pを得る。
鋭さのため m=g−q+2 とし、rj=(j,g+1−j)、j=1,…,g。i=1,…,m に対して Ei={(1,g+1−i),(i,g+1−m)} と置き、D を全 Ei と、j>m の私有需要 rj の合併とする。
Ei の二つの需要区間は [1,i] と [i,m]。両方を一候補で覆えるのは ri だけである。E₁,Em と私有需要は T₀={r₁,rm,…,rg} の q 個を強制し、T₀ は全需要を覆う。全候補の極大担当集合は異なる。
残りの g−q 個に割り当てられる保持確率の総和は高々 B−q。少なくとも一つの内部候補 i は保持確率が p 以下となる。その固定された Ei では、i が残れば一個、消えれば二個を要するので期待比は2−p以上。前述の抽選がこれを達成する。Ei は分布から決められ、実際の抽選結果を見る必要はない。□
今回の発見候補は、どこにあるか
| 構成要素 | 判定 |
|---|---|
| 二候補置換、区間の完全単模性、動的計画法、系統抽出 | 既知。特に抽出法は2026年論文の式・証明と直接一致した。 |
| C1の恒等式とC2の最小比公式 | A0・二次元置換・区間LP双対からの短い導出。公平配分の既知理論とも近く、独立した新原理とは位置づけない。 |
| 本モデルの定式化・厳密値・鋭い g,q,B 保証と反例の整理 | 限定された貢献候補。同一の整理が既存研究にないかは未確認で、新規性未確定。 |
| 固定された将来と、抽選後に選ばれる将来の差 | 上の定理の適用条件を確定する境界。一般的な乱択アルゴリズムの敵対者区別自体は既知。 |
公正な確率割当をLPで設計する発想自体も一般的である。研究としての主張は、この意味保存モデルの将来損失を、厳密に最適化・実現・説明できることに絞る。Grandoni et al. の Set Covering with Our Eyes Closed(SICOMP 2013)は担当写像を事前に固定するモデルであり、保持集合を抽選した後にその中で再最適化する本稿とは異なる。目的や量化順序の違いは、新規性の証明ではなく、比較すべき差分である。
第5版の追加照合:公平配分と最小比
C1の期待値への拡張と τT(S(ri))=2−𝟙{i∈T} の組合せは、A0と二次元の置換補題から得られる短い系である。C2も区間被覆のLP双対を本問題へ特殊化したもので、「最も厳しい部分集合の比が公平水準を決める」形自体を新規性とはしない。
Megiddo, Optimal flows in networks with multiple sources and sinks(1974)の本文、Theorem 4.6・式(4.22)(誌面105ページ)では、公平フローの水準を minA≠∅wk(A)/|A| で定める構成を確認した。Fujishige, Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector(1980)の原著要旨、およびTheory of Principal Partitions Revisited(2009)の要旨・書誌も確認した。後二者は本文未取得である。
本稿の実行可能領域を、これらの基多面体へ帰着する証明は得ていない。従って既存定理の直接の系と断定することも、形の類似を無視して独立の新定理と売り出すこともしない。現時点の貢献候補は、この意味保存モデルでの定式化・厳密値・鋭い保持数保証と反例を一体として整理した点に限定する。
照合語:randomized interval hitting、max-min fair hitting、randomized set-cover retention、representative skyline、lexicographically optimal base、principal partition、max-min fair flow、deficiency form of Hall’s theorem。Hallのdeficiency形は今回、照合候補への追加に留まり、本文照合済みとはしない。直接一致した抽出法と区間双対性は上記本文で確認した。検索結果が不十分な分野もあり、網羅調査は完了していない。次の学術的な判断には、この一体的な定理を確率的被覆・組合せ最適化の専門家に比較してもらう必要がある。
① 意味を保つ削除が、将来の最適性を失わせる
モデル:可能な継続だけを見る
有限で決定的な循環のない遷移系を考える。操作の費用は d 種類の資源の非負整数ベクトルで、経路上で加算する。同じ制御状態 q における残予算の候補集合を R とする。
不等号は座標ごと。観測者が知るのは「その操作列が、いずれかの予算候補の下で可能か」である。これを may 継続意味論と呼ぶ。各候補を生んだ過去の履歴との対応は観測しない。
許す圧縮は T⊆R という既存候補の削除だけ。新しいベクトルを合成したり、捨てた候補を復元したりしない。費用は保持候補の個数とする。候補を符号化するビット数や、任意の抽象表現の最小サイズとは別の尺度である。
実際に可能な継続の費用ベクトル全体を D とする。候補 r は、z≤r を満たす需要 z を担当できる。担当集合を S(r)={z∈D:z≤r} と書く。
候補集合 A から、需要 E をすべて賄うために必要な最小個数。τA(∅)=0。
T が D をすべて覆うことと、Lq(T)=Lq(R) は同値である。T⊆R なので不可能だった語が増えることはなく、可能だった語を一つも失わない条件が、ちょうど費用ベクトルの被覆になる。
A0:最悪の将来損失の正確な公式
D は有限非空、R は有限、T⊆R は D を覆うとする。ここでは任意の有限集合被覆に一般化でき、座標や Pareto 条件は不要である。
= maxr∈R τT(S(r)).
つまり、元の一候補が担当していたことを、残した候補で何個に分ければ代替できるか。その最大値が、将来の需要がどう絞られても起こり得る最悪損失に一致する。
証明
右辺を κ とする。任意の E の最適な R 被覆 U を取り、各 r∈U を、S(r) を覆う高々 κ 個の T 候補で置き換える。合併は E を覆い、個数は高々 κ|U|。従って Λ≤κ。
逆に最大値を取る r を選ぶ。D は非空で覆われるため κ≥1 で、S(r) は非空。将来需要を E=S(r) にすると、元の最適個数は r 一つによる1、残した候補では κ。従って Λ≥κ。□
抽象式では任意の E⊆D を許す。これらすべてが、特定の遷移系の一つの接頭辞の後に現れるとは限らない。後述の等号例・無界例については、実際の正費用の分岐で実現する。
将来の最適性まで保つ削除の条件
A0 から、すべての将来 E に対して最適個数を保つ条件は、各 r∈R について S(r)⊆S(t) となる t∈T が一つ存在することである。したがって、包含に関して極大な、異なる担当集合ごとに一候補を残せばよく、それが最小となる。現在の可能性だけを保つ被覆より、強い要求である。
非空の S(r) について、座標ごとの最大値を並べたベクトルを ⋁S(r) と書く。支配関係による被覆では、
右辺は座標ごとの比較。S(r)=∅ の包含条件は自明に成立する。
d 次元なら、各座標の最大値を達成する需要を一つずつ選べば、選んだ高々 d 個の join が ⋁S(r) と一致する。従って高々 d 個で全体との共同処理条件が決まる。そのため、高々 d 個の需要を一候補で共同処理できるかの保存を確認すれば、全将来の最適性保存を判定できる。2次元ならペアで足りる。これは損失の有無の診断であり、3次元での損失量が3以下だという意味ではない。
A1:資源の数による鋭い境界
R が Pareto 反鎖、すなわち異なる候補同士で一方が他方を全座標で上回ることがなく、T⊆R が現在の全需要 D を覆うとする。
| 資源の数 | 最悪の将来損失 Λ | 達成の強さ |
|---|---|---|
| 1 | 1 | 反鎖は高々一候補 |
| 2 | 1 または 2 | 最初の T が一意の最適解でも2に達する |
| 3以上 | 次元だけによる有限上界なし | 一候補の削除で1対m。最初の T は一意の最適解 |
さらに2資源では、正確な削除を何度繰り返しても、元の未削除候補と比べた損失は高々2である。2回数には増えない。
2資源の証明:左右の二候補で代替できる
この局所置換は Agarwal et al., arXiv:2003.00202v1 (2020), §5.1・Appendix A.14 に既出である。以下の2倍保証は、その既知補題の直接系として示す。
R を第1座標の昇順に並べる。反鎖なので第2座標は厳密に降順になる。一つの需要を担当できる候補の添字集合は、「第1座標を満たす接尾区間」と「第2座標を満たす接頭区間」の交差であり、区間になる。
削除した候補 r の左右で、T に残る最も近い候補を取る。r が担当した需要は T のどこかで必ず覆われる。その担当区間は r と残存候補をともに含むので、その側の最寄り候補も含む。従って S(r) 全体を左右の高々二候補で覆える。A0 により Λ≤2。r∈T なら一候補で足りる。
繰り返し削除した後も、現在の保持集合は元の候補の部分集合であり、現在の需要を覆う。同じ議論を元の候補と直接比較して適用すればよい。途中の上界を掛け合わせる必要はない。□
触れる等号例:中央を捨てると、後で2対1になる
丸=予算候補。小さい四角=将来需要。枠=現在だけ必要な専用需要。
R={l,p,r}。現在の需要は l,r,d₁,d₂。専用需要 l と r が両端を強制するので、T={l,r} が一意の最適解となり、中央 p は削除される。
分岐後は d₁=(1,2), d₂=(2,1) だけが残る。削除前なら p 一つで足りる。T の中では l と r の両方が必要。
失うのは将来の行動ではなく、それらを少数候補で表現する選択肢である。
3資源の無界例
任意の整数 m≥2 に対し、次を置く。
1≤i≤m、R={p,q₁,…,qm}、現在の需要 D={q₁,…,qm,d₁,…,dm}。
R は反鎖である。専用需要 qi を担当できるのは同名の qi だけ。よって T={q₁,…,qm} が一意の最適被覆で、p 一つが削除される。将来の需要が {d₁,…,dm} になると、p はすべてを担当できる一方、残存 qj が di を担当するのは j=i のときに限る。従って将来の最適個数は 1 対 m。□
この表示は上の明示構成の式を示す。数値実験から外挿した上界ではない。
実際の分岐と、意味保存の合成
接頭辞 u の費用を c、到着状態を qu とし、R/u={r−c:r∈R, r≥c} とする。費用の加法性から、
左辺は u に続けて可能な語の集合。従って、全継続の意味を保存した削除は、更新後にも意味を保存する。A1 が示すのは、その先での最適候補数まで保存されるとは限らない、という点である。
正の費用を持つ有限DAGでの等号例の実現
上の2D/3D例のすべての初期予算に c=(1,…,1) を足す。初期状態 q から、専用需要 x ごとに費用 c+x の操作 γx で終端へ進む。また、費用 c の操作 a で q′へ進み、q′から費用 di の操作 βi で終端へ進む。ラベルはすべて区別する。
初期状態では γ が両端または全 qi を強制する。それらは aβi もすべて可能にするので、一意の最適保持集合である。a の後は γ の需要がなくなり、予算から c が引かれるので、上の将来問題がそのまま現れる。空語と接頭辞 a も保存される。全費用座標が正で、遷移系は決定的かつ非巡回である。
第2版:初期解の選び方と、需要の削除数
以下は今回追加した独立証明である。左右二点への置換は既知の補題として使い、その前提を外した場合と、一意性・削除数を組み合わせた場合を調べた。同じ分類定理が文献にあるかは未確定である。
A2:次元・一意性・削除数による鋭い分類
有限候補 R⊂ℕd、有限非空需要 D⊂ℕd、座標ごとの支配による被覆を考える。T⊆R は D の最小個数被覆。将来需要 ∅≠E⊆D について、h=|D∖E|≥1 とする。候補は一律に一個と数える。Pareto 条件は仮定しない。
この条件を満たすすべての有限インスタンスで、比 τT(E)/τR(E) の最大値は次のとおりである。
| 資源の次元 d | 初期最小解の一意性を仮定しない | 初期最小解 T が一意 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | min(3, h+1) | min(2, h) |
| 3以上 | h+1 | h |
全欄で、各整数 h≥1 に対する等号例がある。一意な初期最適解なら需要を一個削除しても損失は起きず、二個以上を削除すると差が生じ得る。
h はこの被覆モデルで削除する異なる需要ベクトルの個数。削除した候補数、更新回数、分岐数ではない。特定のプログラムで到達可能な E だけに制限した場合には、表は上界を与えるが、すべての等号例がそのプログラムで実現するとは限らない。
証明1:二次元では、任意の初期最小解で最大3倍
元候補 p∈R に対し、保持点のうち p 以下のものを Ip={t∈T:t≤p} とする。もし二個以上あれば、それらすべてを p 一個に替えて現在の全需要を覆えるため、T の最小性に反する。したがって |Ip|≤1。
p 以下の需要に限れば、p の右側(第1座標が p より大きい)の保持点は、第2座標が最大の一点でまとめて代替できる。上側の保持点も、第1座標が最大の一点で代替できる。この二群で Ip 以外をすべて覆う。内部の高々一点と合わせ、p の担当集合は高々三点で覆える。A0 により Λ≤3。□
R={p,a,b,c}, T={a,b,c}
E={(1,3),(2,2),(3,1)}, D=E∪{a,c}.
この例では専用需要 a,c が両端を強制し、中央を覆うため b または p が必要。初期最適は三個で、T と {a,p,c} が同率になる。将来 E では p 一個で足りるが、T では三個すべて必要。これが h=2 での鋭い3倍である。
証明2:一意な初期最小解なら2倍に戻る
一意最小の T に、別候補 r に支配される t があるとする。r∈T なら t を消せて最小性に反し、r∉T なら t を r に替えた別の同率最適解ができて一意性に反する。したがって T は R の極大点だけからなる。
R の各候補を極大な支配候補へ置換しても、どの将来 E の最適値も変わらない。極大点集合は二次元 Pareto 反鎖なので、既知の二点置換による上界2が適用できる。前節の三候補例が一意最小かつ h=2 の等号例である。□
証明3:需要を h 個消す場合の、次元によらない境界
この段階では幾何は不要で、任意の有限集合被覆で成り立つ。n=|T|、k=τR(E)、X=D∖E と置く。E の最適被覆 O に、削除需要 X のための T 内の被覆 B を加えれば D を覆う。B は高々 h 個で選べるので、n≤k+h。従って将来の比は高々 n/k≤h+1。
T が一意で、将来に損失 τT(E)>k がある場合を考える。O は T の外の候補を必ず含む。よって O∪B は T と異なる D の被覆であり、一意性から |O∪B|≥n+1。従って n≤k+h−1、比は高々 1+(h−1)/k≤h。損失がない場合の比は1で、やはり h 以下である。□
より強い形。b=τT(X) と置けば、損失がある場合の比は一般に 1+b/k 以下、一意最小なら 1+(b−1)/k 以下。したがって、一意な初期最小解から、残存候補一個で共同処理できる需要群を削除するだけなら、将来最適性は失われない。
h+1 の議論は、再最適化で既知の「需要 h 個の変更による最適値の加法 h 安定性」の基本的帰結として扱う。一意性による h への改善と表全体については、照合できた本文内で同一命題を確認していない。
すべての h・次元での鋭さ
1次元では、実行可能な保持集合の最大点一個が全需要を覆うため常に比1。
2次元・非一意・h=1 には R={(1,3),(2,2),(3,1)}、E={(1,2),(2,1)}、D=E∪{(1,3)}、T={(1,3),(3,1)} を使う。現在は最小二個、将来は2対1。h=2 には上の四候補の3倍例を使う。一意・h=2 には前節の三候補2倍例を使う。一意・h=1 は常に比1。
大きい h に合わせるには、基礎例の候補・需要座標を N=h+1 倍し、h−h₀ 個の需要 (1,j), 1≤j≤h−h₀ を D だけに追加する。全候補がこれらを担当できるので、初期最適・一意性・将来の比は変わらず、削除数だけが h になる。比1の例にも同じ方法を使える。
3次元の非一意列には、前節の p,qᵢ,dᵢ 構成で m=h+1 とし、専用需要は q₁,…,qh だけ置く。これら h 候補に加え、最後の dm のため p または qm が必要なので、全 qᵢ を残した T は初期最小。h 個の専用需要を消すと将来比は h+1。一意列では m=h≥2 として全 qᵢ の専用需要を置けば、将来比 h を得る。h=1 は比1の自明な例でよい。
高次元には、全候補・全需要に同じ正の座標を追加すれば、被覆関係を保ったまま埋め込める。これで表の全欄の上界と達成例が揃う。□
A3:初期解が最適でない場合の鋭い上界
二次元で、T は現在の D を覆う任意の保持集合とする。最適個数からの余剰 s=|T|−τR(D)≥0 に対し、
上の交換論法から |Ip|≤s+1。内部の s+1 点と右・上の二点を合わせればよい。単なる「これ以上一個も消せない被覆」では余剰 s が大きくなり得るので、一定倍の保証にはならない。
すべての s≥0 で s+3 を達成する構成
k=s+1 とし、p=(k+2,k+2)、qᵢ=(i+1,k+2−i)(1≤i≤k)、L=(1,k+3)、U=(k+3,1) とする。T={L,U,q₁,…,qk}、R=T∪{p}、E={q₁,…,qk,(1,k+2),(k+2,1)}、D=E∪{L,U}。
初期最適は強制された L,U に p を加えた三個。T は k+2=s+3 個で、余剰は s。将来 E は p 一個で足りる一方、T では各需要に対応する全 k+2 個が必要。□
反復時の条件。初期需要 D₀ と初期保持集合 T₀ を固定し、s₀=|T₀|−τR(D₀) をその初期値で固定する。以後は候補の部分集合 Tⱼ⊆T₀ と、非空需要 Dⱼ⊆D₀ だけを考え、Tⱼ が Dⱼ を覆うとする。このとき、
理由は |{t∈Tⱼ:t≤p}|≤|{t∈T₀:t≤p}|≤s₀+1 が継承されるからである。各段階を元の R と直接比較するので係数は掛け合わされない。共通の接頭辞費用を差し引く場合も、到達可能な需要・候補を元の座標へ戻して適用する。
削除前にできる改善:支配される候補を置き換える
元候補 R がまだ利用可能な段階で、各 t∈T を、それを支配する極大点 f(t)∈R へ置換し、N(T)={f(t):t∈T} とする。どの将来被覆も点ごとに置換できるので、
したがって、この正規化は現在の個数も将来の全最適値も悪化させない。初期最小解からなら個数は等しく、二次元では2倍保証を得る。同率の初期最小解の中で座標和の総和が最大になる解を選んでも、この性質を保証できる。これは、不可逆な削除に入る前の選択規則である。
補足:2倍未満、すなわち全将来で比1を保証する保持数
単位個数の被覆では、A0により Λ=maxr∈RτT(S(r)) は正の整数。従って Λ<2 ⇔ Λ=1 である。個々の将来 E の比がすべて整数という主張ではなく、全将来にわたる最大値の性質である。
m≥2、rᵢ=(i,m+1−i)、Eᵢ={(1,m+1−i),(i,1)}、D=⋃ᵢEᵢ、R={r₁,…,rm} とする。現在は r₁ と rm が強制され、この二点が全需要を覆うため、一意最小は二個である。
しかし Eᵢ を一候補で覆えるのは rᵢ だけ。初期意味を保存しつつ rᵢ を落とすと、その将来需要では1対2になる。従って、すべての将来で厳密に2未満を保証するには m 個すべての保持が必要。m は任意なので、現在の最小個数が二個という情報だけでは十分な保持数を制限できない。
これは A0 と極大担当集合による特徴づけの具体的な系であり、独立した新原理とは主張しない。各 Eᵢ へ分岐する正費用の有限DAGで実現できるが、任意の表現形式についての記憶ビット数の下界ではない。
ここでの一意性と2倍保証は候補個数を最小化する場合の主張。候補ごとの価格を変えた重み付き問題へ、一意性だけでそのまま移すことはできない。
補論:最初の劣化には、多数の候補の協調が必要なことがある
A0は、すべての将来需要集合を許した最大の損失倍率を、候補一個ずつの担当需要で判定できると述べた。では「需要が何個消えたら、初めて最適性を失うか」も同じ検査で分かるだろうか。この問いでは、多数の削除済み候補を同時に使う解が必要になる。
最初の損失が発生する削除数の厳密な証明書
有限集合 R、D と、D を被覆する保持集合 T⊆R を考える。費用は候補一個につき1。C(O)=⋃r∈OS(r) とおき、損失が起きない場合の最小値を ∞ と約束する。
= min { |D∖C(O)| : O⊆R, τT(C(O))>|O| }.
右辺の候補は、一個の担当需要 S(r) から、候補群の担当需要 C(O) に拡張されている。この式は有限の正確な特徴づけであり、それ自体が高速な計算法を与えるわけではない。
二資源・一意な初期最適解でも、必要な候補数は無制限
任意の m≥3 に対し、2m−1 個のPareto候補を持ち、次の性質をすべて満たす正整数二次元の例が存在する。
- 初期最適解 T は一意で、保持数は m。需要を m−1 個まで削除しても最適性を保つ。
- ちょうど m 個の特定の需要を削除すると、初めて保持側 m 対元集合側 m−1 の損失が生じる。
- その時点で改善できる唯一の解は、削除済み候補 m−1 個をすべて使う解である。
- それでも、削除数を制限しない最大損失は Λ=2 のままである。
したがって、削除済み候補を高々 b 個使う証明書だけを調べる検査は、m>b+1 とすれば最初の劣化を見落とす。これは特定の局所検査の限界であり、あらゆるアルゴリズムに対する計算量下界ではない。
例えば候補が5個なら、奇数番の3個を保持する。3個の専用需要が消えた時点で、削除済みの偶数番2個を併用して初めて改善できる。一個の候補の担当需要だけを残すA0の検査例では、11個もの需要削除が必要であり、最初の劣化を捉えない。なお損失は需要削除に対して単調とは限らないので、「h個まで安全」は削除数≤hのすべてを意味する。
完全な構成・証明と有限検証
Hの公式
右辺で許される O は、E=C(O) とすれば τR(E)≤|O|<τT(E) を満たすので、左辺≤右辺。逆に、損失を生む X に対して E=D∖X の元集合側の最小被覆 O を取ると、E⊆C(O) より τT(C(O))≥τT(E)>|O|、かつ D∖C(O)⊆X。これで逆向きも従う。この公式は初期最適性や幾何を仮定しない。
任意のmを実現する二次元座標
L=m+1 とする。候補と辺需要を次で定義する。
di,a=(Li−a, L(2m−i−1)) (1≤i≤2m−2、0≤a≤L−1).
T={r₁,r₃,…,r2m−1} を保持する。需要Dにはすべての di,a と、奇数 j ごとの専用需要 rj を入れる。座標はすべて正で、需要ベクトルは互いに異なる。候補はPareto反鎖であり、di,a≤rj は i≤j≤i+1 と同値である。つまり候補を道の頂点と見れば、隣接する各二頂点だけが賄える需要が L 個ずつあり、奇数頂点には専用需要が一個ずつある。
初期一意性と最初の損失
専用需要が奇数候補をすべて強制するので、Tは初期の一意な最小被覆である。需要を高々 m 個削除しても、L=m+1 個ある各辺需要は少なくとも一個残る。残った辺需要の被覆は、2m−1 頂点の道の頂点被覆と同じになる。
この道の最小頂点被覆は、偶数頂点全部からなる m−1 個の集合ただ一つである。実際、補集合の独立集合が m 個なら、その並び p₁<…<pm は隣同士の差が2以上で、1≤p₁、pm≤2m−1 より、必ず pi=2i−1 となる。
奇数の専用需要が一個でも残れば、この偶数被覆は不可能になり、元集合側の最適値も m になる。保持側では、各奇数頂点がある辺の唯一の保持端点なので、最適値は常に m。従って高々 m 個の削除で損失が起きるのは、m 個の専用需要をすべて削除した場合だけであり、その時の唯一の改善解が、削除済み偶数候補全部である。
二次元Paretoの上界から Λ≤2。一方、任意の偶数候補が担当する両隣の辺需要は、元候補なら一個、保持候補なら両隣の二個を要するので Λ=2。その一候補の担当需要に絞るには、(2m−4)(m+1)+m 個の需要削除を要する。真の最初の削除数 H=m との差は、m とともに拡大する。
最小の失敗集合に関する補助的性質
X≠∅が包含極小の失敗削除集合、E=D∖X、k=τR(E)なら、τT(E)=k+1。また、元集合側のどの k 個の被覆 O も C(O)=E を満たす。初期Tが最適なら、失敗集合Xは必ず非空である。各 x∈X を戻すと損失が消え、需要一個の追加で最適値は高々1しか増えないため、
すべて等号となる。Oが削除済みのxまで覆えば最後の最適値はk以下となり矛盾するので、C(O)=Eである。これは初等的な感度解析として扱う。
検証の範囲
全3候補×3需要の被覆関係について、初期最適解450件を列挙し、Hの公式を直接の全需要削除列挙と照合した。有限のHを持つ54件、包含極小の失敗集合54件で補助的性質も確認した。二次元構成は m=3,…,8 の各例で元候補・保持候補の全部分集合を列挙し、一意性、H=m、必要な削除済み候補数 m−1、Λ=2 を確認した。有限検証は一般証明の代用ではない。
補論:その損失へ、実際に到達できるか
前節は任意の将来需要に対する保証である。実際のプログラムでは、到達できる接頭辞だけを調べればよい。しかし、この絞り込みにも計算上の難しさがある。
正整数の二資源費用を持つ有限・決定的DAGを考える。費用と予算は二進表現。R={ℓ,p,r} はPareto反鎖、T={ℓ,r} は初期言語を正確に保存する一意の最小支持集合とする。実行可能な接頭辞uの後、元の将来言語を再現する最小候補数をκR(u), κT(u)と書く。意味の保存は続くが、再圧縮に必要な個数が異なる場合がある。
後続が二本の終端辺だけである指定状態で、κT(u)>κR(u)となる接頭辞が存在するかはNP完全。上記の初期正確性・一意性を約束しても成立する。指定状態を外した任意接頭辞の問題はNP困難で、ここで示す上界はΣ2Pである。後者のNP完全性は主張しない。
還元と、途中に偽の損失が生じないことの証明
SUBSET SUMの正整数w₁,…,wₙと目標0≤B≤W=Σwᵢから、M=W+1、H=(n+B+M,n+W−B+M)を作る。
n段の選択を置き、第i段は異なるラベルで費用(wᵢ+1,1)または(1,wᵢ+1)を選ぶ。続いて費用(M,M)の共通辺aで指定状態q*へ進み、そこから費用(1,2),(2,1)の終端辺βL,βRを置く。初期状態には、費用がℓそのもの、rそのものの私有終端辺γℓ,γrも加える。全ラベルを状態ごとに区別すれば決定的で、状態数・符号長は多項式である。
選んだ重みの和をs、δ=s−Bとすると、q*での残予算は次のとおり。負座標を持つ候補は消える。
a以前の選択鎖上の接頭辞費用は各座標n+W以下で、三予算すべてに収まる。aの直後の空語や二つのβについても、pで可能な語は端点の和集合で可能である。一方γℓ,γrは各端点を強制する。従って初期Tは正確かつ一意の最小集合である。
δ=0ではpが両βを覆い、各端点は片方だけを覆うので比2。δ=1,2,3ではrだけで元の将来言語を覆い、δ=−1,−2,−3ではℓだけで覆う。それ以外はq*に到達できない。従って指定状態での損失はs=Bと同値。指定状態の空語と二つの操作だけを調べればよいので、接頭辞を証明書としてNP所属も従う。
さらにSUBSET SUMがNoなら、a以前にも損失はない。空接頭辞では初期最適性により両側とも2。非空接頭辞で選択鎖上にいる場合は私有終端辺γが既に使えない。そこからaを越える可能な継続がなければ、どちらの端点も全言語を覆う。あるなら完成和のδ≠0に対し、δ=3ではaまでの語、δ=2ではaβL、δ=1ではaβRが元候補では可能でpでは不可能となる(負δは左右対称)。よってpはその時点の全言語を単独被覆できない。終端では空語だけなので比1。これで任意接頭辞問題のNP困難性も従う。
一般DAGのΣ2P上界:接頭辞uと、各端点の単独被覆失敗を示す二つの接尾辞を存在的に選び、全接尾辞vについて「元候補で可能ならpで可能」を確認する。DAGでは各語長が状態数以下である。pの単独被覆には全称条件が必要なので、指定状態の場合のNP所属を一般化してはいけない。
Bⱼ=maxr∈Rrⱼとする。全到達状態・累積費用対(q,c)での損失は、固定三候補なら次の算術演算数で判定できる。
これは予算値に依存する擬多項式時間であり、二進入力長の多項式時間ではない。単項表現や多項式に抑えた予算なら多項式時間になる。
監査算法の定義と正しさ
各状態qの接尾辞費用集合Fqを[0,B₁]×[0,B₂]に切り詰め、空語費用(0,0)を含めて逆位相順DPで作る。その二次元累積個数をHq(x,y)=|Fq∩([0,x]×[0,y])|とし、負の添字は0とする。前向きDPでは初期予算のいずれかに収まる到達累積費用cを列挙する。
候補部分集合U⊆Rが覆う接尾辞費用数は、定数個の矩形に対する包含排除で得られる。
U⊆Rなので、Uによる言語の完全被覆はNU=NRと同値。異なる語が同じ費用でも可否は一致するため、語数を数える必要はない。高々8個の候補部分集合を調べ、元候補と保持候補の最小サイズを比較する。空間はO(|V|(B₁+1)(B₂+1))。同じ(q,c)を共有する全語を列挙する必要はなく、各対の証拠語を一本復元できる。ビット計算量には数値のビット長の因子が掛かる。
有限検査:n=1,…,4、wᵢ∈{1,2,3}、全目標Bについて972入力・28,307到達状態/費用対を検査。初期一意最適性、全接頭辞での損失と部分和の同値、指定状態の条件、全8部分集合の被覆計数が一致した。一般の証明を置き換える検査ではない。
② 忘却の影響は、いつ初めて見えるか
モデル:可能世界を増やす忘却
有限世界集合 W の大きさを n とする。精密な文脈は非空集合 C、忘却後は C⊊D⊆W。可能性が増えるので、分かっていることは減る。固定命題 P⊆W に対する観測は「すべての可能世界で P が成り立つか」、すなわち S⊆P である。
一つの置換 f:W→W を繰り返し適用する。時刻 t の文脈は ft[C], ft[D]。最初に次が成り立つ t≥0 を露呈長とし、存在しなければ∞とする。
これは「C側だけが P を支持する」という向きのある比較である。C={c}, D={c,z} でも、c と z の出力がどちら向きでも異なればよい通常の二状態識別問題とは異なる。
B1:可逆更新における正確な最大露呈長
n≥2、k≥1、一つの置換更新、1≤|C|≤k の下で、全モデルにわたる最大の有限露呈長は、正確に
達成例は、忘却によって一世界だけ追加した D=C∪{z} で作れる。「|C|が高々k」と「ちょうどk」は区別する。
証明:上界と達成構成
上界。露呈時に P の外にある世界の始点 z∈D∖C を一つ選ぶ。C の世界と z が属する巡回路は高々 k+1 本、総長は n 以下。それらの状態は周期 L=lcm(巡回路長) で戻る。露呈が有限なら同じ条件は最初の一周期内に現れるので、t≤L−1≤Gk+1(n)−1。
下界。G を達成する巡回長が t≥2 本なら、最初の t−1 本の座標0を C とし、最後の一本の座標0を z とする。更新は各巡回で+1。P は C側の各巡回では末尾 ℓi−1 だけ、z側の巡回では末尾以外を含む。露呈条件は全巡回で時刻≡−1 mod ℓi、したがって初回は L−1。互いに素である必要はない。
一本の巡回だけで最大値を達成するときは、異なる c,z を置き、C={c}, P={f−1(c)} とする。長さℓの巡回なら初回露呈はℓ−1。n≥2では G≥2 なので、異なる二点を取れる。残りの世界は使わない固定点にすればよい。□
5世界で、最初の違いは5回目
C は2周期の一点 c₀、追加世界 z₀ は3周期。P={c₁,z₀,z₁} とする。C単独と忘却後Dの観測は、時刻0〜4まで一致する。
| 更新回数 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 精密なCがPを支持 | × | ○ | × | ○ | × | ○ |
| 忘却後DがPを支持 | × | ○ | × | ○ | × | × |
lcm(2,3)−1=5。空集合の自明な支持には依存しない。
| 世界数 n | 元文脈の上限 k | 最大有限露呈長 | 達成する巡回長の例 |
|---|---|---|---|
| 5 | 1 | 5 | 2, 3 |
| 10 | 1 | 20 | 3, 7 |
| 10 | 2 | 29 | 2, 3, 5 |
| 20 | 1 | 98 | 9, 11 |
| 20 | 2 | 279 | 5, 7, 8 |
| 20 | 3 | 419 | 3, 4, 5, 7 |
文脈サイズを制限しなければ、Gn(n) は既知の Landau 関数 g(n)。最大露呈長は g(n)−1 となる。巡回長の最小公倍数を使う現象や関数そのものを新発見とは扱わない。Landau 関数の一次資料。
第2版の照合:単項オートマトンに正確に帰着する
各世界 q について Lq={at:ft(q)∈P} と置くと、追加世界 z が露呈を起こす時刻は、次の単項言語の語長に一致する。
置換なら、同じ巡回路内のマーカー条件を許可位相の集合にまとめられる。したがって、総状態数が n 以下の、高々 k+1 個の巡回単項DFAの共通受理語問題である。この還元はここでの直接的な数学的分析であり、既存論文に同じ意味論の式が載っていると主張するものではない。
共通語問題は Fernau–Hoffmann–Wehar (2021)、巡回オートマトンの積構成は Rauch–Holzer (2022), §3・§3.5 で扱われる。B1の厳密式自体の既載箇所は未特定だが、周期の最小公倍数と位相合わせで直接導ける。このため既知構造の系と評価し、新しい数学的原理の候補には数えない。
補注:一つの非可逆な全域更新まで拡張する
置換の代わりに一つの全域関数 f を反復する場合も、1≤|C|≤k、n≥2 の最大有限露呈長は厳密に
ここだけの h は巡回部分までの最大過渡長であり、A2の需要削除数とは別である。C と証拠世界 z がすべて巡回に入るまで h ステップかかれば、巡回外に少なくとも h 世界があり、残り n−h 世界の周期は G 以下。したがって h+G−1 が上界。h=n−1 なら一本の尾と固定点しか残らず、周期に入った後の露呈は不可能である。過渡部分での露呈は n−2 以下で、n巡回の下界 n−1 に収まる。
達成には、最大の最小公倍数を与える巡回群の一つへ長さ h の尾をつなぎ、追加世界 z をその尾の始点に置く(h=0 なら巡回の座標0)。尾全体を P に含める。C側の各巡回の許可位相を h−1、z側の不許可位相を巡回の末尾にすれば、最初の露呈は h+G−1。一巡回だけのときも、Cの許可点を z の末尾と異なる点に置き、Cの初期位相をずらせば同じ時刻を得る。
n=6,k=1 では置換の5に対し全域関数では6。n≤5の全写像・全C,z,P、計7,616,664件およびn=6の達成例で確認した。ただし、これも尾と周期を持つ単項構造の拡張である。Krawetz–Lawrence–Shallit, §2–3 が一生成変換モノイドとSzalay (1980)の先行研究を説明する。k付きの式そのものを彼らの定理と帰属することはしない。
複数の全域決定的更新:最短の更新列を選ぶ
有限世界 W、非空 C⊊D⊆W、観測命題 P⊆W と、モデルごとに固定された有限の許可更新族 F⊆{f:W→W}を考える。列 w=f₁…fₘ∈F* に対して fw=fₘ∘…∘f₁ とし、空列 ε は恒等写像とする。このモデルの最短露呈長を
条件を満たす列がなければ∞。初期状態で露呈していれば0。
まず固定したモデル内で露呈させる最短列を選ぶ。次に |W|=n≥2、1≤|C|≤k の下で、F,C,D,P を含む全モデルの有限な δF の最大値を Δk(n) とする。この最大化は、更新列を敵対的に選んで露呈を遅らせる操作ではない。
露呈する列と、その終点でP外に出る追加世界の始点 z∈D∖C を一つ取る。追う状態は「C の現在像 S」と「z の現在像 x∉S」の組。全域決定的像では 1≤|S|≤k が保たれる。x が一度 S に入ると以後も S に含まれ、その証拠では露呈できない。許可更新ごとに辺を張った組状態グラフで、最短路には反復がない。組の総数 nΣbinom(n−1,j) を数えると上界を得る。
各固定 k について上界は Ok(nk+1)。k+1本の互いに素な巡回長を各々Θk(n)に取れば、一つの置換だけを許すモデルでΩk(nk+1)を達成する。例えば固定した別々の素数の冪で、各々 n/(k+1) 以下の最大のものを使える。従って各固定 k について、n→∞ のとき Δk(n)=Θk(nk+1) である。
断言更新:許可する断言と、空文脈の規約
今度は、あらかじめ固定した有限族 𝒜⊆2W の A だけを使い、αA(S)=S∩A と更新する。これは世界上の全域関数の像とは異なり、非空文脈を空にすることがある。最短露呈長 δ𝒜 は、上と同じ条件を満たす最短断言列の長さとする。本文の基本規約では∅⊆P も支持と認め、更新後の空文脈を許す。初期 C は非空のままである。
U=C∖P と置く。露呈の証拠になれるのは z∈D∖(C∪P)。その z を含む許可断言 A だけを選び、除去集合 U∖A で U を覆う最小個数を τz(U) とする。被覆不能なら∞、U=∅なら0と定めると、
証拠zの候補がなければ、右辺は∞。
断言の共通部分を B(空列では W)とすると、露呈条件は U∩B=∅ と、P外の追加世界がBに残ること。従って集合被覆と正確に対応する。有限な被覆があれば U の各点を消す断言を一つずつ選べるので、有限露呈長は |U|=|C∖P| 以下。U=∅ なら有限値は0である。
すべての A⊆W を自由に使える場合は、証拠 z が存在し U≠∅ なら A=W∖U の一手で露呈する。証拠が存在し U=∅ なら初期から露呈し、証拠がなければいつまでも露呈しない。このため、断言族を指定することが遅延を論じる上で必要になる。
空文脈を許さない場合との違い
各段階で更新後の C を非空に保つ規約なら、最終的に残る g∈C∩P も必要となる。z と g の両方を含む許可断言だけを使う集合被覆数を τz,g(U) とすれば、最短長は minz∈D∖(C∪P), g∈C∩Pτz,g(U)。この式の候補がない場合も∞である。断言は集合を縮めるだけなので、最終的に g が残るなら途中でも非空が保たれる。有限な値には同じ |C∖P| 上界が成り立ち、さらに |C∖P|≤|C|−1。
違いが現れる最小例は W={c,z}、C={c}、D={c,z}、P=∅、𝒜={{z}}。空文脈を許すと一手後の C=∅、D={z} で露呈する。非空維持では露呈不能である。
複数の一般更新での指数的遅延は、部分集合同期などの既知理論に強く重なるため、独立した新規成果の中心には置かない。Vorel の部分集合同期研究。
先行研究との境界
2026 09 17 の照合を、外部レビューに基づき補った。節・付録番号は本文を実際に確認した上記arXiv版の番号であり、掲載版の同番号を指すものではない。本文の定義・証明に確認できた重複を優先した。以下の「未確認」は、該当定理が存在しないという意味ではない。
| 今回の項目 | 最も近い確認先 | 判定 |
|---|---|---|
| 2Dの二点置換 | Agarwal et al., arXiv:2003.00202v1 (2020)、§5.1・Appendix A.14。雑誌版:ACM TALG 18(4), Article 40 (2022) | 削除点の左右の最寄り残存点で区間を救済する証明が明記される。A1の証明核心は既知。 |
| 幾何的候補の削除 | Liu–Wang (2024)、§4.1 | 特定の削除可能点を左右二点で代替し、元の需要の最適解を残す。任意の保持集合と全将来需要を比較するA2とは条件が異なる。 |
| 将来の部分需要に備える | Grandoni et al., Set Covering with Our Eyes Closed (2008)、§1 | 需要ごとの担当写像を事前固定する universal set cover。今回の「保持候補内で毎回最適化」と区別する。 |
| 需要削除による最適値の変動 | Jansen–Mömke–Schumacher, arXiv:2512.16805v1、§1.1・§3。掲載版:IWOCA 2026, LNCS 16587, pp.370–384 | 変更後も全候補を使える計算量問題。需要の定数変更と最適値の加法安定性は既知。§3.4には専用需要で一意最適を作る構成もある。 |
| A2・A3の分類 | 上記文献とその引用先を照合 | 3/一意2、s+3、一意性によるh改善を合わせた同一定理は、読めた本文内で未確認。証明済みだが新規性未確定。 |
| B1の遅延式 | 単項DFAの共通語、巡回オートマトンの積、Landau関数 | 正確な還元を明示できたので、既知構造の鋭い系へ評価を下げる。同一式の掲載箇所を確定したという意味ではない。 |
追加照合:代表点・antichain・近似Pareto集合
| 一次資料と確認箇所 | 近い構造 | 今回との違い |
|---|---|---|
| Lin–Yuan–Zhang–Zhang, Selecting Stars: The k Most Representative Skyline Operator (ICDE 2007)、§2.1・§4・§5.1 | skylineのk点を選び、支配される相異なる入力点数を最大化。2Dでは動的計画法、3D以上ではNP困難。 | kは入力。既存結果は固定需要上の最大被覆の計算量、今回の表は全将来部分需要に対する最適個数比。計算困難性と比の無界性は別の主張。 |
| De Wulf–Doyen–Henzinger–Raskin, Antichains: A New Algorithm for Checking Universality of Finite Automata (CAV 2006)、§3・定理2–3 | 包含関係で極大/極小な状態集合だけを保持し、閉集合を表現する。 | A0の極大担当集合も同じ順序的構造を持つ。現在の需要を覆う最小集合への追加削減は、単一候補には支配されない候補も消し得る。 |
| Papadimitriou–Yannakakis, On the Approximability of Trade-offs and Optimal Access of Web Sources (FOCS 2000)、§2・定理1–2 | 各目的座標を近似するε-Pareto集合の存在と構成を扱う。 | 今回近似するのは被覆の候補数であり、座標ごとの支配判定は厳密に保つ。座標の近似から境界需要の実行可能性保存は直接従わない。 |
この比較から、用途は「通常の支配削除に加えて、現在の需要を覆う候補数も削減した場合の将来損失保証」と述べるのが正確である。単一候補が持つ担当集合を、別の単一候補がすべて代替する削除なら全将来の最適値を保てる。複数候補の協働で現在の被覆だけを保つ削除では、その先の再最適化の自由度が失われ得る。
Chatterjee–Doyen–Henzinger–Raskin, Generalized Mean-payoff and Energy Games (FSTTCS 2010), §1–2 は、多資源の初期予算を扱う背景文献としても近い。ただし本稿の有限・決定的DAGと非負消費に対する保証を、二人ゲーム・無限実行・正負の資源変動へそのまま適用することはできない。既存のantichain固定点アルゴリズム全体への適用保証や、VASSの初期予算問題の一般解法までは示していない。
新規性の断定を妨げる、具体的な未照合資料
Bilò–Widmayer–Zych, Reoptimization of Weighted Graph and Covering Problems(WAOA 2008、刊行2009)は出版社の書誌・要旨まで、Zych, Reoptimization of NP-hard Problems(ETH博士論文、2012)は参照先までを確認したが、本文を取得できなかった。Mikhailyuk (2010)も要旨確認に留まる。ここに一意性や類似の交換補題が含まれていないとは言えない。
検索は universal set cover、候補削減・coreset、区間 hitting set、reoptimization、unique optimum、unary DFA intersection、Landau、transformation monoid とその引用追跡を中心に行った。専門索引の全収録・全被引用文献の網羅調査ではない。
第1〜3版の差分をどう述べるか
同一命題の掲載箇所が見つからなくても、短い交換論法から得られる通常の観察と評価される可能性は残る。A0・極大担当集合の特徴づけや、需要削除の基本論法に一意性を加えた補題を、それぞれ独立した新原理とは位置づけない。主な検討対象は、仮定を横断した鋭い定数分類と、その具体的な圧縮モデルでの用途である。
妥当な現時点の主張は、「既知の区間置換と再最適化の基本論法を用い、候補を初期解へ永久制限した際の損失を、次元・一意性・需要削除数で鋭く分類した。同一分類の先行掲載は未確定」である。「新しい2倍定理を発見」「先行研究に存在しない」とは述べない。
また、Bolander–Buriganaの有界双模倣縮約や、Bispingの多次元予算による同値性検査とは表現・最小化の対象が異なる。今回の結果を任意モデルの最小状態数定理へ拡大解釈しない。
査読対応
第5版の追加査読
C1の前提再掲、C2の容量・交換補題、公平配分との比較と新規性表現の限定、記号の適用範囲、六候補例のk=2・3同率、再現手順と既定上書き、冒頭表の適応的将来の条件、全表のcaptionを修正した。数値・主要定理は変更していない。
第3版の査読対応
提供された外部レビューの6項目を、本文・定義・一次資料に照らして検討した。主要な分類定理の値を変える反例は見つからず、以下の定義・説明・書誌を修正した。
| 指摘 | 対応 |
|---|---|
| 複数更新と断言更新の定義不足 | 固定した許可更新族、最短更新列、モデルにわたる最大化を分離。断言の空文脈支持を明示し、非空維持版も区別した。 |
| 全将来で「2未満」の意味 | Λの整数性から「全将来で比1」と同値であることを明記。 |
| 高々d需要による判定 | 非空担当集合の座標ごとのjoinによる同値式を追加。 |
| A3の非累積保証 | 初期D₀,T₀と余剰s₀を固定し、以後Tⱼ⊆T₀,Dⱼ⊆D₀とする条件を明記。 |
| h=0の検証 | A2のh≥1とは別に、比1を確かめる境界検査として件数を分離。 |
| 書誌・近接研究 | 会議・雑誌掲載情報を更新し、参照したarXiv版を特定。representative skyline、antichain、ε-Paretoとの目的・保証の違いを追記。 |
断言を自由に選べば一手という指摘は、露呈可能な追加世界がある場合に成立する。追加世界がすべてP内なら露呈できない。また、これらの書き足しと既知文献の追加によって、学術的新規性が確定するわけではない。
検証と再現
証明は本文の一般論証である。以下の計算は、境界例・定義・添字・実装の取り違えを検出するための有限検査であり、LeanやRocqによる形式検証ではない。
| 検査 | 範囲 | 結果 |
|---|---|---|
| C1–C3:独立した区間族の監査 | 1〜4候補の全1,094非空区間族、2,870保持予算。27,921将来期待値・4,254抽選結果・8,340貪欲最適性比較 | 分布LPと周辺確率LPが一致。有理数による抽選・被覆・期待値検査を通過 |
| C1–C3:元候補全体との独立比較 | 193事例・262有限ゲームLP。支配候補を含む80事例、重複担当集合を含む67事例。元の保持集合1,095列、将来制約9,005行を比較 | 厳密ソルバーと数値LPの最大差2.22×10⁻¹⁶。抽選・被覆・周辺確率・期待比は有理数で確認 |
| 最初の劣化・非局所性 | 3候補×3需要の初期最適解450件。二次元の明示構成m=3〜8 | H公式・一意性・必要な協調候補数を確認 |
| 到達可能な損失 | 部分和972入力・28,307到達状態/費用対 | 初期一意最適性、全接頭辞と部分和の対応、被覆計数が一致 |
| 第3版:更新の定義・断言の両規約 | 断言134,304モデルを空許可/非空維持の両方で確認(n=2,3は全断言族、n=4は高々2断言)。複数全域更新36,512モデル(n=2は全更新族、n=3は高々2更新)。自由断言1,808ケースと境界例 | 文脈対のBFSと被覆式/証拠世界グラフが一致 |
| A2・A3の追加検証 | 3候補×4需要の全4,096系(h≥1の一般境界44,100件・一意性境界23,982件。別にh=0の比1を一般3,150件・一意1,713件で確認)。2D格子300例・全将来240,544件。次元1〜4・h=1〜8の64達成例、s=0〜8の9達成例 | 上界・一意性・等号・正規化を確認 |
| Bの全域一更新 | n=2〜5の全写像・全C,z,P、7,616,664件とn=6の明示例 | 尾を含む公式と一致 |
| A0の正確な損失公式 | 3候補×3需要の全512 incidence行列。被覆可能な保持集合1,183件、その将来部分集合8,281件 | 一致 |
| A1の区間補題 | 1〜5候補上の全非空区間族・全実行可能保持集合、合計 203,769 組 | 上界2を確認 |
| A1の明示構成 | 2D等号例、3D m=2〜9。一意な初期最適・将来最適・正費用の共通移動 | 一致 |
| B1の最大露呈長 | n=2〜10。置換の巡回型ごとの代表、全非空C・全z∉C・全P、合計 261,741,128 件 | 公式と一致 |
| 追加の診断 | 関係更新1,000件(seed 9172026)で二通りの探索を比較。二進カウンタ例 k=1〜8 | 一致 |
第1〜3版の再現コードと第4版の厳密ソルバー、安定性・到達可能性の検証はPython標準ライブラリのみ。第4版の独立LP比較コード2本はNumPy・SciPyを使う。Bの既定値はn≤6。記録されたn=2,…,10の数値結果の再計算には python verify_forgetting.py --max-n 10 --output result.json を使う。保存済みのforgetting_results.jsonは、n=2〜6とn=7〜10を別々に実行して統合した履歴をexecution_batchesに記録している。上の単一コマンドは同じ数値ケースを計算するが、その過去の実行履歴や集計用メタデータを同一JSONとして再生成するものではない。追加診断は補助コードとして含むが、指数現象を新規成果として主張しない。
第2版の検証は python verify_v2.py で標準出力だけへ結果を出す。ファイル保存は python verify_v2.py --output fresh_v2_results.json と明示し、既存ファイルへの上書きは拒否する。以前の実装の保存先はCWDではなくスクリプトと同じディレクトリだったが、既定で既存記録を上書きする問題は修正した。
第4版は python solve_randomized_retention.py で例の最適分布を生成し、python verify_randomized_v4.py と python verify_randomized_audit_v4.py で独立比較する。有限ゲームの将来需要は、全元候補で論理的に同値な制約だけをまとめ、需要数9以下では全需要部分集合との一致も照合した。
記録された検査結果を表示
第4版:最適乱択保持の厳密ソルバー
A:再現コードを表示
B:再現コードを表示
第2版の分類:再現コードを表示
全域一更新:再現コードを表示
第3版の定義監査:再現コードを表示
このHTMLは外部スクリプト・フォント・画像を読み込まず、オフラインで本文・図・再現コードを閲覧できる。文献リンクの閲覧には通信が必要。HTML構造・埋込ファイル一致・JavaScript構文と簡易DOM実行を確認した。現在の実行環境にはブラウザ本体がなく、実ブラウザでの描画確認は未実施。