NP困難って何なの？

[0001 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 12:33:32.589 ID:djTg2OTv0]

教えてくだせぇ

[0002 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 12:33:56.342 ID:djTg2OTv0]

NP
NP完全
NP困難

これなに？

[0003 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:34:42.881 ID:SD8ZUF0hd]

https://video.twimg.com/ext_tw_video/1607773532565667840/pu/vid/720x1280/d8W-L7SwVzcZD3XO.mp4?tag=12

[0004 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:35:07.224 ID:RRL2d3M10]

パターンが多いやつ

[0005 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 12:35:19.406 ID:djTg2OTv0]

ナップサックはDPで割りと簡単に解けるのに、巡回セールスマン問題は簡単には解けないのなぜ？

[0006 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:38:03.153 ID:ZXeGJdkgd]

なんでだろ～なんでだろ～

[0007 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:38:26.440 ID:RRL2d3M10]

重さは1つだけど距離はいっぱいあるから

[0008 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:40:10.664 ID:RGcGvx0Cr]

>>5
ナップサック問題も問題の制限によってはNP困難やNP完全になる

[0009 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 12:41:24.386 ID:djTg2OTv0]

>>8
まずNP完全とNP困難の違いを教えてくれぇぇ

[0010 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:43:02.312 ID:E8fwr5hC0]

そもそもDPが使える背景には最適性原理がある

[0011 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:48:41.181 ID:nGuxZ9GSa]

>>9
NP困難:NPと同程度以上に難しい問題
NP完全:NP困難のうちNPのもの

[0012 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 12:49:35.745 ID:djTg2OTv0]

調べたわ

P←解くのも検証も簡単
NP←解くの困難、検証簡単
NP完全←これが簡単に解けたらP=NPだわ
NP困難←これを解くためにはNP完全解かなきゃならぬ

であってる？

[0013 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:50:56.649 ID:nGuxZ9GSa]

>>12
間違ってる

[0014 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 12:51:15.514 ID:djTg2OTv0]

>>13
どこが？

[0015 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:51:37.578 ID:CwrteNVf0]

>>12
調べてそうだったんならそうじゃないの

[0016 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:52:26.026 ID:LQrc9pBQd]

🐙には教えない

[0017 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 12:52:43.961 ID:nGuxZ9GSa]

>>14
完全と困難

[0018 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 12:56:37.317 ID:djTg2OTv0]

NP完全←NP問題かつ任意のNPを解くためには多項式時間で帰着できる問題←つまり任意のNPと同等以上に難い問題←つまりこれが多項式時間で解けたらP=NP
ってことじゃね？

[0019 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 12:57:52.814 ID:djTg2OTv0]

やっぱりわかんなくなったわ

[0020 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 12:58:09.755 ID:djTg2OTv0]

NP完全かつNP困難ってどういうことじゃ

[0021 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 13:01:24.954 ID:nGuxZ9GSa]

>>20
定義からしてNP完全はNP困難に含まれるぞ

[0022 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 13:04:56.363 ID:djTg2OTv0]

>>21
なるほどつまりNP完全な問題は全てNP困難なのか
じゃあNP困難かつNP完全でない問題はなんなんだ…
巡回セールスマン問題とか

[0023 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 13:08:56.430 ID:uwVNmkDS0]

ナマペニス困難？

[0024 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 13:13:50.445 ID:nGuxZ9GSa]

>>22
co-NP
多項式時間で検証できない問題
巡回セールスマンはそれが正しいか確認できないからco-NPだな

[0025 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 13:16:02.422 ID:djTg2OTv0]

>>24
なるほど、巡回するルートが与えられてもそれが最小かは確認出来ないってことか
なるほどねぇ

[0026 以下、5ちゃんねるからVIPがお送りします🐙 2023/01/19(木) 13:17:29.609 ID:djTg2OTv0]

とりまNP、NP完全、NP困難の違いは分かった
で、ナップサック問題はNP困難に属するわけだがなんでDPで割りと解けるの？
巡回セールスマンはDP使っても全然解けないのに

[0027 以下、5ちゃんねるからVIPがお送りします 2023/01/19(木) 13:58:05.877 ID:u1py2Szfr]

Pは効率よく解けるやつ
NPは非効率で解けるやつ
NP完全は非効率で解けてPにもなったりするやつ
NP困難は解けるアルゴリズムが見つかっただけのやつ

であってる？