【NHK】笑わない数学【P≠NP】

**それでも動く名無し** · 2022/08/03(水) 23:10:09.37

見るで

**それでも動く名無し** · 2022/08/03(水) 23:46:27.43

>>451
確かに定義はそうなんだけど、解が正しいかどうか多項式時間で確認可能
ていうのもTM使った定義と同値だからそこまで勉強しなくても別に大丈夫

**それでも動く名無し** · 2022/08/03(水) 23:46:57.72

>>452
NSは解析的には解けんのやろ？
無理なんちゃうんか

**それでも動く名無し** · 2022/08/03(水) 23:47:18.68

総当りせずとも裏技があるよって話なんかな
図書で読みたいな

**それでも動く名無し** · 2022/08/03(水) 23:48:21.20

>>454
すまん語弊があったわ、どんな問題でもちゃうなよう知らんが
総当たりのゴリ押しでしか解けん問題がざっくり言えばNPやったっけ

**それでも動く名無し** · 2022/08/03(水) 23:49:37.26

>>456
現状ゴリ押しでしか解けないが、効率的な方法があるかもしれないのがNP問題

**それでも動く名無し** · 2022/08/03(水) 23:49:47.56

あーみればよかったわ

**それでも動く名無し** · 2022/08/03(水) 23:50:18.62

>>436
はえー
やっぱ数学ってすごいわ

**それでも動く名無し** · 2022/08/03(水) 23:51:00.98

>>453
だから「多項式時間で検証可能」って概念の厳密な説明に結局TMが必須やん

**それでも動く名無し** · 2022/08/03(水) 23:51:18.14

>>458
先週のワイ

**それでも動く名無し** · 2022/08/03(水) 23:51:57.59

ワイこれ見逃し配信見たくてNHK+に登録してもうたわ

**それでも動く名無し** · 2022/08/03(水) 23:55:05.93

>>460
実は計算複雑性理論では計算モデルを限定してないから、TMじゃなくてもいい
計算ステップの定義も適当だからザックリn^kで計算できるってわかればいいのよ
そこを何か固定しなきゃ気持ち悪いって言うならTMでもラムダ計算でもどうぞお好きにっていう

**それでも動く名無し** · 2022/08/03(水) 23:57:17.52

なんGってどの分野にもガチ勢いるよな