NP完全な問題を視覚的にこねる
https://gyazo.com/268219434b23b97c112e774e0b72a0dd
これは一体…？cFQ2f7LRuLYP.icon
Summer498.iconさんのとこで見たtakker.icon
判定マシンに三つのスイッチがつながっている
table:凡例
緑 OK
赤 NG
灰 OFF
黄 ON
どういうルールを表すか！？
オフになってるのが３つ繋がってると、死
オンになってるのが２つ繋がってると、死
判定マシンに繋がっているうちの1個のみがオンになっているときだけOKを出す。
OFF=false, ON=trueとすると、
$ \def\off{\textcolor{gray}{\text{OFF}}}\def\on{\textcolor{orange}{\text{ON}}}\def\ok{\textcolor{green}{\text{OK}}}\def\ng{\textcolor{red}{\text{NG}}}\begin{array}{cccc}\text{input}&\text{input}&\text{input}&\text{output}\\\off&\off&\off&\ng\\\on&\off&\off&\ok\\\off&\on&\off&\ok\\\off&\off&\on&\ok\\\on&\on&\off&\ng\\\off&\on&\on&\ng\\\on&\off&\on&\ng\\\on&\on&\on&\ng\\\end{array}
真理値表で表せないかな～と思ったけど、そういう構造でもなさそう？takker.icon $ (x+y+z)(\bar x+\bar y)(\bar y+\bar z)(\bar z + \bar x)
オレ語ですSummer498.icon
table:aa
ONの数
0 NG
1 OK
2 NG
3 NG
$ 100i点ほしいtakker.icon
https://gyazo.com/9c51e2cc5ab1af2c498f8e484b9083a0
黒は判定マシン
いまから、この黒丸をすべてOKにしたい。
これは一体…？
who1.icon出現yosider.icon
青は何なんだkumatako.icon
赤丸はNG
右上さん
https://gyazo.com/e56dcf0447e71077a1786b10121148f7
キュート！
赤と青と緑はスイッチ
二種類の赤は同じ
前提ではなかった 今から示しますよ〜
Alice, Bob, Charlieyosider.icon
全ての判定マシンをOKにしたい
例題の解答
ルール：真ん中の判定マシン2つをOKにしなければならない、に従うと
赤丸で示された2つのスイッチは、このルールにおいて必ず同じ状態（ON/OFF）を取る
https://gyazo.com/d1afe6f3b19dadea09d071ab7dd984c9
何だこの酷い絵は、と思ったけどこの絵をかけるのは発表者であるワイしかおらんなSummer498.icon
左側がONになったとき、隣接する判定機がNGにならないために上下は必ずOFFになる。
よって右側は隣接する判定機をOKにするためにONになる。
上下のどちらかがONになると、隣接するスイッチはすでにOKになる
NGにしないために、赤丸のスイッチは両方ともオフになる。
判定マシンをOKにした状態で、その状態であり得るスイッチの組み合わせを考えればいいわけだtakker.icon
この「黒丸の判定機」が増えるごとに、「すべてをOKにする」の難易度が上がっていく。
この場合の「難しい」「難易度が上がる」はコンピューターでも解くのが難しくなるという意味
ここで言うコンピュータとは、ゲーミングPCであっても、スパコン富岳であっても、量子コンピュータであってもよいSummer498.icon
https://gyazo.com/c100d6028836582aaaa57b9f153f63a6
このように、4つにするだけでもなかなか難しくなる。
https://gyazo.com/2ad471ee4b2bb562ce0e321318e1ba4c
上記の判定機において、同色の丸で示されるスイッチは、「必ず状態が同じ」になる法則が適用される。
青は青と、緑は緑と、赤は赤と、常に同じ状態（ON/OFF）になる
つまり、2^3=8通り、(ON|OFF)の置き方があるのかtakker.icon
(ON|OFF)しか置けないときもあるのかな？
https://gyazo.com/163a7816c1c92ae85fc9349bf2ade7ee
一番上の黒丸を光らせるために、黒丸としか隣接していないスイッチをONにすると
NGにしないために両端の赤はOFFになる
同時に、同値である中央の赤もOFFになる
また、青と緑は≠の関係になる
青がONのとき、緑は必ずOFFになる
緑はONのとき、青は必ずOFFになる
これを満たさない場合は「すべての判定機をOKにする」ができなくなる
んだとおもうcman.icon
独自記法なのだろうかyosider.icon
yes
https://gyazo.com/3915eede25f5eb8745a398fa8bd35139
スイッチは3色だけではなく、例えばこのように配線を組むと6色になる。
解が存在しないグラフがあるtakker.icon
https://gyazo.com/4dfa4d24b438f69e49102b3ed8cb2f29
この装置は矢印で示されたスイッチが左では「OFF」でないと成り立たない
しかし右に繋がっている装置では矢印のスイッチは「ON」でなければ成り立たない。
矛盾した状態になるため、「すべてをOKにする」ということができなくなる。
このような状態になっているかどうか判定することが難しい。
ところでこの図は何と呼べばいい？takker.icon
判定マシンは黒丸のこと
CNN(畳み込みニューラルネットワーク)？takker.icon
やっぱ数理論理学じゃないかtakker.icon
スイッチはそれ以外の丸
bool変数
グラフ全体は名前あるのかな
いつの間にかししとうと言われてるの草takker.icon
獅子唐Summer498.icon
解判定が難しいのかtakker.icon
オイラーの橋のやつは簡単にわかるのに
オイラー閉路は簡単に解けるSummer498.icon
ハミルトン閉路問題は解くのが難しい
解判定ですら難しい、そんなニュアンスがある気がするSummer498.icon
余談：前はこのように書いていたので混乱するSummer498.icon
https://gyazo.com/f31e3bda84385ce35ec7286ee62b2aef
旧記法を書きにくくなりがちなのわかるtakker.icon
（脱線）リンクするとき文字列を選択して[押す方がはやくないですか？yosider.icon
この問題は答え合わせは簡単で、問題を解くのが難しいことがわかっている
答えるのが簡単な問題はP
答えるの=問題を解くの
全部OKになってるかを確認すればいいので答え合わせは簡単
解くときにどうすればOKになるかとか出来ない状態になってるかとかをやるのが難しい
例：素因数分解takker.icon
解くのは大変
でも確認するのは簡単
でも本当に解くのが大変だという証明がされていないSummer498.icon
場合によっては証明できないと証明される問題もあるからなあtakker.icon
$ \cal P\ne \cal NPは現在試されている方法だと証明できないことが示されている
\neしらんかったtakker.icon
$ \neq\ne
クソ問題じゃねえかtakker.icon
クソ問題とか言うなwwwSummer498.icon
未知の数学を使わないといけないということか
だれか未来に行って新しい数学入手してきて
これが嬉しい場合もあって、「じゃあどっち使っても自由やんけ！」と数学の自由度が増えて嬉しくなることもある
アルゴリズムを作るタイプのプログラマは NP 完全問題の隣で働いている職業Summer498.icon
少し難しい問題に対してアルゴリズムを考えるとすぐ NP 完全問題が顔を出す
それこそクソ問題じゃねえかtakker.iconなんて思ってられないほど
なので、「やばそう」と言う勘と、
ホンマにNP完全やって証明(確認)する力を持っておくとよい
なお、ある程度の規模の問題は近似アルゴリズムを用いることで爆速で解けるようになっている模様
厳密アルゴリズムの進化も目覚ましい