問題タブ [computability]

(p 入力) が停止するように入力が存在するかどうかを判断できるプログラム (may-halt? p) はありますか?

簡単な対角化を試みましたが、(may-halt? diag-may-halt) が true でなければならないということしかわかりません。プログラムが存在するかどうかを証明するのには役立ちません。

そのようなプログラムは存在しますか？

次の素粒子物理学のアニメーションに注意してください。

これは、単純ではありますが、離れた場所でのアクションを伴います。つまり、各ティックで、原子は任意に離れた他の原子と相互作用します。これは、ローカル ルールしか持たないセル オートマトンでは不可能です。したがって、私は疑問に思います:同様に見える素粒子物理学の振る舞いを表示できる最も単純なオートマトン エンコーディングは何ですか?

チェスのゲームの動きを教えて、誰が勝つかを宣言した場合、勝者が実際に勝つかどうかを多項式時間でチェックできないのはなぜですか? これは、私の理解ではNPの問題になります。

SAT2016 を定義 = {\phi | \phi は、最大で 2016 句を含む CNF 式です}。P \neq NP を仮定すると、SAT2016 は NP 完全ですか?

各節のリテラルの数は制限されていないため、節の数が一定に制限されている式の充足可能性をチェックするための多項式時間アルゴリズムが存在するかどうかはすぐにはわかりません。

あなたのアイデアは大歓迎です。

サブセットのサイズがあり、すべての整数が正（ゼロではない）であるサブセット合計問題のバリエーションがあります。k

オンラインで見られるように、この問題は疑似多項式時間で動的計画法を使用してかなり解決できます。

NPCこの問題がであるか、P( であると仮定して) であるかを判断する必要がありP!=NPます。

私はサブセットサムの問題から削減しようとしましたが、すべての整数がゼロより大きくなければならないという制約に問題がありました。それ以外の場合は、入力をkゼロの整数で埋めただけです。

問題の正式な定義:

L={<S1,S2,...,Sn,T,k>|There exists a subset I of S1,...,Sn of size m which sums up to T}