いつCSPの地平線の拡大を止めるべきですか？

Question

いつCSPプランナーの地平線の拡大を止めるべきですか？ 具体的には、検索とのアーク整合性がある地平線で失敗すると、アーク整合性がすべてのより長い地平で失敗することを意味する制約充足問題プラナーの条件があるかどうか。

Answer 1

プランナーが非常に一般的な場合、答えは「いいえ」にする必要があります。

「この行列の各行はチューリングマシンのテープに対応し、行iはステップiの後のチューリングマシンの状態と最後の行のスナップショットですチューリングマシンが停止したことを示します。

「この制約条件を満たすマトリックスが見つかりました」は「このチューリングマシンが停止しました」に相当し、https://en.wikipedia.org/wiki/Halting_problemはチューリングマシンやその他の一般計算が停止しているかどうかを調べる唯一の方法です停止するかどうかを確認してください。