takehikom https://blog.hatena.ne.jp/takehikom/ わさっきhb https://takehikom.hateblo.jp/ 情報教育 今日は2問．関連する話なので． なぜ「35を素因数分解せよ」は「問題」じゃないの? 35でも，一千万桁を超えるような合成数でも*1，何らかの方法でその個別問題の答えを求め，記録しておけば，あとは同一の個別問題が出たら，記録していたのを書き並べるだけだからです． ここから「問題を解く手間は，その問題に属する，有限個の個別問題を解く手間から測るものではない」というアドバイスが引き出せます．「1個」から「有限個」に拡張しましたが，それでも，前処理をするか，先人が出した解答を記録しておき，個別問題が来たら適切な答えを返すだけで，実質的な計算をせずに「解が求められた」ことになってしまいます． 512ビッ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftakehikom.hateblo.jp%2Fentry%2F20070718%2F1184706737" title=" P=NP問題を理解するためのステップ〜問題は無限集合 - わさっきhb" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2007-07-18 06:12:17 rich https://takehikom.hateblo.jp/entry/20070718/1184706737 1.0 100%