[過去ﾛｸﾞ] P=NP (428ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

4(2): 2020/03/30(月)23:23 ID:zmYBSMz5(2/3) AAS
平面上の有限個の点(ユークリッド距離)にインスタンスを制限してもいいけど, それもNP困難だからね.
提案手法はまだ突っ込みどころが多い気がします.
(というかよく理解できません)
なお, P=NP 問題が(万が一)肯定的に解決されるなら, それはおそらく非構成的な証明になるだろうと思います.

---

71: a4 ◆L1L.Ef50zuAv 2020/04/02(木)10:31 ID:gWEkLHdd(18/21) AAS
EnglishのWikipediaで「Travelling salesman problem」を見てます。すると、>>4
さんの仰る通り、

「When the input numbers can be arbitrary real numbers, Euclidean TSP is a
particular case of metric TSP, since distances in a plane obey the triangle
inequality. When the input numbers must be integers, comparing lengths of
tours involves comparing sums of square-roots. Like the general TSP,
Euclidean TSP is NP-hard in either case. With rational coordinates and
discretized metric (distances rounded up to an integer), the problem is
NP-complete.[28] 」

[28]Papadimitriou (1977)は、
省3

---

156: a4 ◆L1L.Ef50zuAv 2020/05/25(月)02:02 ID:G6Yn3ivH(2/6) AAS
オイラー先生はとりあえず信用することにして、公理ってなんだろう？と素朴に思って
見ました。公理的集合論とかあるけど、あれだけじゃ自然数が出てくるだけで、
ペアノの公理と来るし、解析学をやろうと思うと別の公理が。まず考えたのは、
人間の前頭葉と海馬の神経を真似たＴ語による公理群のマルチエージェント
シミュレーションです。バナッハタルスキーの逆理があるため、公理という考え方
が間違ってる？ということもあるかもしれません。でもP=NPはそういう問題では
ありません。有限なメモリ内で解決すればＴ語で証明が表現でき、すなわち、
自動定理検証などができる、と考えてます。とりあえず僕はＣＰＵを信じて、
Ｔ語の推論があっているというところから考えることにします。現実的には
>>4さんのクヌース先生の言葉でも仰る通り、非構成的な証明かもですけどね。

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.761s*