ut-bioinformatic https://blog.hatena.ne.jp/ut-bioinformatic/ バイオインフォ学生あれこれ https://ut-bioinformatic.hatenablog.jp/ 情報科学・数学 はじめに 定期テストに向けて、Karp's Reduction の流れに沿って、諸々の問題の NP 完全性を示すことができるように勉強する必要が生じた。 ここでは、ナップサック問題が弱 NP 完全問題であることを、Partition が弱 NP 完全問題であることを利用して、証明する。 Partition について Partition における入力は、 個の要素からなる整数集合 である。 出力すべきは、 ある で、 \begin{equation} \sum_{i \in X} a_i = \sum_{i \not \in X} a_i \end{equation} を満たす X は存在するか… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fut-bioinformatic.hatenablog.jp%2Fentry%2F2023%2F01%2F17%2F014610" title="ナップサック問題（判定版）が弱NP完全問題であることの証明 - バイオインフォ学生あれこれ" 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 2023-01-17 01:46:10 rich https://ut-bioinformatic.hatenablog.jp/entry/2023/01/17/014610 1.0 100%