P≠NP予想

P≠NP予想というものを聞いたことがあるでしょうか。
ミレニアム数学問題にも挙げられるコンピュータサイエンスのよく知られた難問で、計算量クラスPと計算量クラスNPが等しくないという予想です。定期的についに解決した！という論文が発表されることでも知られています。
メモリや時間と言ったリソースを制限すると、計算できる問題が減ります。制限のかけ方に応じて計算できる問題の集合が変化するのでそれらを計算量クラスと呼びます。計算量クラス同士の関係は色々と調べられています。中でもPとNPは非常に有名な計算量クラスです。
NPと対になる計算量クラスに、co-NPというものがあります。NPとco-NPは違う計算量クラスなのですが、自分は初見では違いがピンと来にくい気がしたので解説記事を書いてみることにしました。
以下では判別問題を考えます。つまり出力がyes or noである問題です。「2+3は？」といった問題ではなく、「2+3は6か？」といった問題です。

P

計算量クラスPをまず考えます。Pは、チューリングマシン（チューリングマシンがよくわからない人は普通のプログラミング言語で実装することを考えればまあ問題ないです）で多項式ステップでyesかnoか答えられる問題の集合です。多項式時間とは入力長の多項式のステップで計算できるということです。普段触れるアルゴリズムで解ける問題は大体このPに入っているでしょう。

NP

NPのNはNon-deterministic、つまり非決定性の略です。NP問題とは、非決定性チューリングマシンで多項式時間でyesかnoか答えられる問題の集合です。非決定性チューリングマシンとは毎ステップの遷移に複数の選択肢があっても良く、それらを全ての可能性を計算して（チューリングマシンが分裂してそれぞれを計算するというイメージでも良い）どれかの選択肢においてyesであったらyesを返し、そうでなかったらnoを返すようものです。
分かりやすいイメージとして大量の人で分業して問題を解くというものがあります。無限にスレッドを作れる計算機で計算するというイメージでも良いかもしれません。ただし、毎ステップ定数倍に増えるだけであり分業する人数は高々計算時間の指数です。
非決定性チューリングマシンは大量の人のうち一人でもyesを返せばyesを、そうでなければnoを返します。

co-NP

ではco-NPの定義は何なのでしょうか？co-NPとは「yesとnoをひっくり返すと、NP問題になるような問題の集合」です。一見、yesとnoをひっくり返しても特に条件に大差があるようには思えません。簡単な例を考えることでこの違いを実感してみましょう。

"is合成数"はNP

整数が入力し、その整数が合成数ならばyesをそうでなければnoを返す問題を考えます。これはNPであることがすぐ分かります。
n bitの長さの入力$x$があったとしましょう。まず、$(x-2)$人の作業する人を用意します。$2$から$x-1$の数字を各々に割り振って、割り切れるか確認してもらいます。もしも与えられた数字で$x$を割り切ることが出来たら、大声で「YES!!」と叫んでもらいます。一人でも「YES!!」と叫んだ人がいれば合成数なのでyesを返せば良く、皆が計算を終えてもシーンとしていればnoを返せば良いでしょう。$x$が高々$2^n$乗程度であるので人数も大丈夫です。

"is合成数"はco-NPか？

is合成数のyesとnoをひっくり返すとisPrimeになります。つまりisPrimeがNPがどうかを考えればよいのです。先ほどと同じアルゴリズムで計算しようとしてみます。
x人の作業する人を用意します。$2$から$x-1$の数字を各々に割り振って、割り切れるか確認してもらいます。yesとnoをひっくり返すために、与えられた数字で$x$を割り切れなかったら、大声で「YES!!」と叫んでもらうことにしてもらいます。
すると、素数の時は全員が「YES!!」と叫ぶのでYESを、合成数の時も一部の人を除いて「YES!!」と叫ぶのでYESを返します。
大失敗です。

この非対称性は授業を受けると感じることができます「わからなかった人はいますか？」と質問した時は分からなかった人が素直に返事をすれば問題がありませんが、「全員分かりましたか？」と質問して分かった人が素直に反応すると教室が大混乱してオワオワリです。

以上の失敗を踏まえて、どうすればisPrimeに対して分業によって効率よく答えることが出来るか考えてみます。

原始根

isPrimeがNPであることを示します。つまり、合成数ならば皆が黙り素数の時だけ数人が「YES!!」と叫ぶような分業の仕方を考える必要があります。ここでちょっとした数論の知識を用います。素数Pに対しては原始根が存在するという有名定理があります。原始根とは、

a^0, a^1, \ldots ,a^{p-2}

が$\mod p$で全て異なるような元の事です。つまり$\mod p$の世界で任意の数字が$ a^k $の形であらわすことが出来るような$a$の事です。乗法群の生成元ですね。
しかしながら$x$が合成数の時、$\mod x$の世界でこのような元を取ることは出来ません。$x$と互いに素な数を何乗しても$x$と互いに素のままで、$x$と互いに素でない数は何乗しても$x$と互いに素ではないからです。

つまり、$2$から$x-1$の数字を各々に割り振り、原始根になっているか確認してもし原始根であったら「YES!!」と叫んでもらうことにすると、一人でも「YES!!」と叫んだ人がいれば素数なのでyesを返せば良く、合成数ならばみんな黙っているのでnoを返すことが出来ます。

あとは、多項式時間で原始根なのかどうかを判定できれば勝利です。$a^0$から$a^{p-2}$まですべて計算して確かめると、入力長の指数時間かかってしまいます。以下、良い感じに原始根を判定する方法を紹介します（ですます調を一時的に辞めます）

原始根なのかを多項式時間で判定する

原始根は位数がp-1の元とも表現することが出来る。位数とは、$a^x \equiv 1 \pmod{p}$を満たすような最小の正整数。
フェルマーの小定理によりPが素数ならば$a^{p-1} \equiv 1 \pmod{p}$は必ず成立する。

ここで、$a^y \equiv a^x \equiv 1 \pmod{p}$ の時、xとyの最大公約数を$d$とすると, $bx+cy=d$なる整数$b,c$が取れ、$a^d \equiv a^{bx+cy} \equiv (a^x)^b(a^y)^c \equiv 1$となる。
よって$p-1$が$a^x \equiv 1 $を満たす最小の数でないとき、$p-1$の約数で$a^x \equiv 1 $を満たすものが存在する。
又、$a^x \equiv 1 \pmod{p}$ならば$a^{nx} \equiv 1 \pmod{p}$である。

以上より、$a^{p-1} \equiv 1 $かつ、$ x = {p_1}^{q_1}{p_2}^{q_2} \ldots {p_m}^{q_m} $ と素因数分解した各$p_i$について、$a^{x/p_i} \not \equiv 1 \pmod{p}$を満たすことを確認すれば原始根であるか判定できる。

素因数分解をうまくやる

どうにかして素因数分解をする必要がある。まず、$x$の素因数は高々$\sqrt{x}$であり、素因数の個数は高々$\log_2 x$である。$\log_2 x = n$として、$(p_1,\ldots,p_n)$という素因数分解の候補を作る。候補の数は高々$x^n = 2^{n^2}$個であり、多項式時間で分担することが出来る。
素因数分解の候補が与えられた人は、まず全ての積が$x$であるかどうかを判定する。もしも全ての積が$x$であった場合は各$p_i$が素数であるかどうかを今考えているアルゴリズムで再帰的に判定する。

$c\geqq 2$を定数として、入力$x$として、このアルゴリズムを用いて素数判定をするとき必要な時間を$S(x)$として、$S(x) \leqq n^c$であることを帰納的に示す。($n = \log_2 x$)

\begin{align}
S(x) &= n^2 + S(p_1) + \ldots   S(p_n)\\
&\leqq  n^2 + (\log_2 p_1)^c + \ldots  +(\log_2 p_n)^c \\
&\leqq  n^2 + (\log_2 p_1 + \ldots  +\log_2 p_n)^c \\
&\leqq  n^2 + (\log_2 x)^c \\
\end{align}

示された。
以上よりisPrimeはNP問題である。

NPとco-NPの違い

以上の例を見ると、NPとco-NPが全然違う話であることが実感できると思います。isPrimeはNPかつco-NPです。しかし一方の証明はもう一方の証明より段違いにめんどくさいものでした。やれやれ。

ここで注意することとして、co-P=Pであるということがあります。普通のチューリングマシンは途中で分裂していないので、最後にyesとnoを反転するだけで良いのです。
実はisPrimeは多項式時間で解ける、つまりPであることが知られています。非決定性チューリングマシンは決定性チューリングマシンの上位互換なので、PならばNP、co-Pならばco-NPです。isPrimeがPであるという強い知識を用いるとisPrimeはNPかつco-NPということはすぐ分かります。
P=co-Pより、「P=NPならばNP=co-NP」であることが分かります。対偶を取れば「co-NP≠NPならばNP≠P」です。co-NPとNPが違う計算量クラスであることが示せればミレニアム問題が解けてしまう訳です。是非みなさん頑張ってみてください。解決したと論文を書けば、「月刊P≠NP解決」の仲間入りを果たせます！