NP(n) + P(N-n)

• Development of Var activities (2019-07-11)

ふと思ったのだが、first UIP になりうる変数はどれくらいだろう。 industrial problems でのコア（バックボーン？）はとても小さいはずだが、そもそもそれは矛盾変数はどれくらいであると言うことを意味するのだろう？　 少ないようでもあり、いや、複数回矛盾を起こすものが少ないだけのような気もする。 1 回の矛盾に対して 1 つの first UIP が決まるのだからそして別に 1 対 1 ではないのだから、 first UIP になる変数の個数は意外に小さいのではなかろうか。

CHB4 でやってみた。

まず解ける問題での時間進化。

タイムアウトする問題

この問題では初期状態が終わると、矛盾もその原因も小集団に停滞していると言うことか。 それはリスタートですら抜け出せないと。

ということで、

• 矛盾を起こす変数はせいぜい 1 割程度。その約半数は複数回矛盾を起こす。
• first UIP 変数の個数は矛盾変数の個数のさらに半分程度。その半分は複数回選択される。
• ただし例外もある。Timetable-1 では複数回矛盾する変数の方が first UIP 変数よりも少ない。

では、矛盾回数や選択回数を元に活性度を決めればより速く求解が進むのでは？ 解けなかった Timetable-1 に適用してみる。

個数の増加に停滞が見られず、安定して増加し、あっという間に解くことができた。 残念ながら、この変更した変数活性度には一般性はなく、他の問題では役に立たない。 機械的な切り替え戦略もうまくいかないようだ。

2019-07-24

この尺度は重要かもしれない。増加率は意味ありげな変化を示している。 増加がゆっくりな部分はハードコアにあたるのではないだろうか。 EMAを二つ用意して増加率の傾向の時間変化を記録してみた。 緑線がこの尺度。赤線は矛盾変数。青線はこの段階では無視してほしい。

• FUIP集合と矛盾変数集合の相関は極めて高い。同一と言ってもいいくらい。
• 極めてゆっくりと変化し、変動が少ない。
• 長期にわたって減少する期間がある。これこそハードコアの求解区間ではないだろうか。