Mathematics
graph
complexity
computation
More than 1 year has passed since last update.

はじめに

この記事は壁 Advent Calendar 2017用に内容を(少し)変更いたしました。

数学界隈での「壁」と言えば、やはり未解決問題でしょう。
有名なのはクレイ研究所が提示したミレニアム問題ですね。

ということで、P vs NP 問題に繋がる未解決問題にチャレンジしています。最近、アカデミックとは別系統で活躍されている方々を見て、自分も情報発信していきたいと考えた次第です。Qiita は TeX 記法が使えるのが魅力です:laughing:

P vs NP 問題

計算理論界隈には計算複雑性理論という分野があり、計算量クラスというものに関心が持たれています。ここで、計算量とは決定問題(入力に対して複数の解集合の中から一つを出力する問題)において、入力が与えられてから結果出力に至るまでの時間がどれくらいかかるかを表す指標であり、計算量クラスとは計算量を元に決定問題を分類したものを表します。

以下で定義される2つの計算量クラスがあります。

  • class P: 多項式時間で結果が出る問題集合
  • class NP: ある解候補が与えられたとき、多項式時間でその解候補が正解か否かを判別できる問題集合

ここで、計算量が多項式時間とは、入力サイズを $n$ として出力までに要する時間が $O(n^k)$ $(k$ は定数$)$ かかることを示します。なお、$O()$ はビックオー記法といい、計算量の大きさを表す指標として用いられています。例えば、計算時間が $\sum_{i=0}^{k} c_i n^i$ ($c_i$ は定数) かかる場合、ビックオー記法による計算量は $O(c_k n^k)$ となります。

定義より $P \subset NP$ は明らかですが、$P = NP$ かどうかは重要な未解決問題となっています。この問題はクレイ数学研究所ミレニアム問題の一つとして賞金がかけられたこと、問題が比較的理解し易いことから、多くの人達の関心を得るところとなっています。

問題間の関係

問題集合を計算量で分類する場合、多項式還元という概念が重要になります。NP問題の集合を $Q$ として、ある問題 $q_a \in Q$ の入力列を別の問題 $q_b \in Q$ を利用して解けるとして、$q_a$ から $q_b$ への変換にかかる計算量が多項式時間であるとき、$q_a$ から $q_b$ へ多項式還元可能であるといい、$q_a \le_p q_b$ で表します。不等式で表されるように、$q_b$ は $q_a$ と同等か、それより多くの計算量がかかることを示しています。

NP完全

$q_a \le_p q_b$ かつ $q_b \le_p q_a$ となる二項関係 $q_a \sim q_b$ を導入します。ここで、

  • 反射律($q_a \sim q_a$)
  • 対称律($q_a \sim q_b$ $\rightarrow$ $q_b \sim q_a$)
  • 推移律($q_a \sim q_b \land q_b \sim q_c$ $\rightarrow$ $q_a \sim q_c$)

が成立する問題集合を同値類として計算量クラスを考えます。そして、$q \ge_q q_c$ for $q \in Q, \forall q_c \in Q$ を満たす問題 $q$ を NP完全問題と呼び、この問題が属する同値クラスが NP完全となります。

充足可能性問題

NPに属する問題の一つに充足可能性問題(SAT問題)があります。これは、真偽値(True/False) をとる論理変数 $x_i$ と以下に示す論理演算子

  • 否定: $\bar{x}$
  • 和: $x_a \land x_b$
  • 積: $x_a \lor x_b$
$x_a$ $x_b$ $\bar{x_a}$ $x_a \land x_b$ $x_a \lor x_b$
True True False True True
True False False False False
False True True False False
False False True False False

からなる論理多項式が True となるような論理変数の組を見つける問題です。論理多項式はCNF-SATに変換することができます。これは、以下に示すように各項が論理変数の和で表され、各項を積算したものになります。

$\prod_{i=1}^n(\sum_{j=1}^{m_i} x_{i,j})$
$=(x_{1,1} \cdots \lor x_{1,m_1}) \cdots \land (x_{n,1} \cdots \lor x_{n,m_n})$

一般のSAT問題は NP完全問題ですが(Cook-Levin Theorem)、各項における論理変数の数が $2$以下のものは 2-SAT と呼ばれ、クラスPに属していることが知られています。一方、論理変数の数が $3$以下のものは 3-SAT 問題と呼ばれています。一般のSAT問題は 3-SAT 問題へ変換できることから、3-SAT 問題もまた NP完全問題となります。

NP完全問題の例

SAT問題などのNP完全問題を起点として、問題 $q$ へ多項式還元を行うことができれば、$q$ もまた NP完全問題となります。NP完全問題はグラフ問題に数多く見られます。一例として、ハミルトン路問題があります。これは、与えられたグラフの全ての頂点を一回だけ通るパスがあるかどうかを問う問題です。

P=NP or not?

P $=$ NP かどうかを求める上で、幾つかの戦略があります。

  • P $\neq$ NP
  • P $=$ NP
  • 証明できない(ZF公理系とは独立)

とはいうものの、この分野の大多数の研究者は P $\neq$ NP と考えています。

NP完全と P の間にある計算量クラス

もし、NP完全と P が異なる場合、これらの間には NP完全にも P にも属さない計算量クラスがあるとされています(NP-intermediate)。グラフ同型問題がこの計算量クラスに属しているのではないかと言われていますが、これもまた未解決問題です。グラフ同型問題は、与えられた $2$つのグラフが同型かどうかを判定する問題です。ここで、グラフ $G_a$ と $G_b$ が同型とは頂点間の接続関係を維持した状態で、$G_a$ の頂点から $G_b$ の頂点への全単射が存在することにあたります。

この分野の多くの研究者は NP が P とは異なると考えています。これに対する標準的な方法は、既に知られている計算量クラス、ないしは独自に計算量クラスを定義して、それらの計算量クラス間に存在するであろう非可逆性(異なる計算量クラスに属する問題 $q_a \in Q_a$、$q_b \in Q_b$ において、$q_a \le_p q_b$ かつ $q_b \not \le_p q_a$ となる計算量クラスの組がある)の存在を証明しようとしています。

P=NP へアプローチ

一方、NP完全問題のどれか一つでも多項式時間で解くことができることが示せれば、NP完全問題を含む全ての計算量クラスは Pと同じとなります。とはいうものの、直接 P$=$NP を示そうとする研究者は皆無と言って良いでしょう。多くの研究では、限定した問題において多項式アルゴリズムがあることを示すか、アルゴリズムを改良して計算量の下限を探索しているようです。殆ど全ての研究者が P $\neq$ NP と考えているため、正面から P$=$NP を主張してしまうと、全く相手にされないという背景からあるように感じています。

個人的感想

P vs NP 研究では既存の数学領域(代数や解析等)とはほぼ独立している感があります。研究手法も手詰まり感があるようです。

さて、NP完全と P の間にそのどちらにも属さない計算量クラスが存在する場合、無限個の計算量クラスが存在することなります。それを暗示するかのように大量の計算量クラスが生み出されています。

個人的には、計算量クラスが無限にあるとすると矛盾が生じる気がしています。(個人的な能力の限界により)証明はできないのですが、問題集合 $Q$ は加算無限と思われます。これに対して、計算量クラスが無限にあるとすると、個々の計算量クラスには問題が無限個あるはずで、そうすると加算無限では足りない気がするのです。そのようなことから、私は P $=$ NP ではないかと思っていたりします。(この部分は証明は無いので自己判断をお願いします)

「P $=$ NP だと世界がひっくり返るからありえない/不可能だ」という意見を耳にすることがあります。果たしてそうでしょうか。ここには $2$つの誤解があるように思います。

  • 定数項の問題
  • 準最適解で良いこと

定数項の問題

計算量が $O(n^{1000000000})$ と $O(2^{n \times 0.000000001})$ のどっちが実用的には軽いと言えるでしょうか。前者は多項式時間で解ける問題で、後者は多項式時間では解けません。でも、実用的には入力サイズが比較的小さい、ないしは準最適解を許容することで問題を分解、入力サイズを小さくできる場合などが多く、後者の方が早く計算できるのです。

同じように、P $=$ NP が正しかったとして、$O(n^{1000000000})$ と $O(n^{0.000000001})$ を比べてみると、やはり前者は実用には耐えられない訳です。P $=$ NP だからといって、暗号等のセキュリティ問題が瓦解する訳でもありません。

準最適解で良いこと

NP問題は組み合わせ最適化問題を形式化したものです。確かに最適解が求められた方が良いでしょう。しかし、実用を考えたとき、準最適解で十分な場合がほとんどです。そして、準最適解を求めるのであれば、多項式時間アルゴリズムで無くとも、十分に早いアルゴリズムが知られている問題も多々あります。

まとめ

たとえ、P $=$ NP だったとしても、世界がひっくり返ることはありません。私個人としては、本研究に対する阻害要因は P $\neq$ NP (であるはずだ) という思い込みが非常に強いことにあるのではないか、と思うのです。また、賞金がかけられていること、誰でも手が届きそうな問題設定であることから、疑似数学の一翼となってしまったことも、ブレークスルーを阻害している原因になっている気がしています。