ut-bioinformatic https://blog.hatena.ne.jp/ut-bioinformatic/ バイオインフォ学生あれこれ https://ut-bioinformatic.hatenablog.jp/ 情報科学・数学 はじめに 大学で学んだ多項式時間還元について、日本語記事でわかりやすいものが見つからなかったため、ここに記す。数ヶ月後におそらく試験で出題されるので、その試験対策としても。 blog 末尾でも述べるつもりであるが、Garey と Johnson による黒い本 Computers and intractability. を参考にしている。 解くべき問題の整理 Vertex Cover を判定問題にする必要がある。を与えられた自然数とし、命題を以下のように定める。 命題 VC: の頂点からなる被覆 VC が存在する。 命題 3-SAT: 「リテラルの数、節の数がそれぞれ である論理積標準形 が充足… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fut-bioinformatic.hatenablog.jp%2Fentry%2F2022%2F12%2F20%2F014937" title="＜NP 完全性 (Karp&#39;s Reduction)＞3-SAT から Vertex Cover への多項式時間還元について（polynomial reduction 3-SAT to VC） - バイオインフォ学生あれこれ" 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 2022-12-20 01:49:37 rich https://ut-bioinformatic.hatenablog.jp/entry/2022/12/20/014937 1.0 100%