現実的計算可能性

手に負えない問題

プログラムが実行可能：計算時間が問題(入力)のサイズ（表現長）の多項式で抑えられる
　素朴べき乗　　　　　　　　　　　　：実行可能でない
　高速べき乗、選択法、クイックソート：実行可能

手におえない問題：実行可能なプログラムが存在しない問題

以後、問題をyes/no問題に限定する。

パズル．多項式時間プログラムを実効可能なプログラムとすることの是非を論ぜよ。

非決定性プログラム

非決定性プログラム：非決定性命令を含むプログラム
　非決定性命令：次の動作を有限個の候補の中から選べる
　計算：次の動作をうまく選んだ時に正答yesを正しく計算できればよい
　　　　⇔可能な計算の中に正答yesを正しく計算するものがあればよい
　　　　　（no と答える場合があってもよい）
　計算時間：正答yesを正しく計算するものの中での最短時間としてよい
但し、正答がnoのときにyesと答える場合があってはいけない。

定理．非決定性プログラムでt(n)時間で計算できる問題は、
決定性プログラムでa^t(n)時間(aは選択肢数の最大値)で計算できる。
略証：すべての選択肢を試行錯誤の虱潰しで調べればよい。

P、NP

クラスP:決定性多項式時間プログラムで解ける問題
クラスNP：非決定性多項式時間プログラムで解ける問題

P⊆NP。　　P≠NP か否かが有名な未解決問題 (ミレニアム問題)

オイラー路の存在判定問題∈P
　∵)オイラーの定理があるから
ハミルトン路の存在判定問題∈NP

ハミルトン路を非決定的に選択できれば、それがハミルトン路であることの検証は多項式時間で可能
Pに属すか否かは知られていない

NP問題の別表現
証拠が与えられれば、その答えがYesであることを、問題(入力)サイズの多項式時間内に検証できる問題。

NP完全問題

NP問題pがNP完全：問題pを解くプログラムM_pから、すべてのNP問題qに対して、qを解く多項式時間プログラムM_qを多項式時間で作れる問題

NP完全問題のどれか１つでもP問題であれば、P＝NP
つまり、NP問題の中で、もっとも難しいと考えられる問題

Cookは充足可能性判定問題がNP完全であることを示した(1971)。

充足可能性判定問題
与えられた論理式の値を真にする変数値の割り当てが存在するか否か判定する問題

パズル．P=NPであれば、どのようなことが言えるか。

証明のアイディア

M_P：NP問題Pを解く非決定性多項式p(n)時間プログラム（チューリング機械）
　M_Pはサイズnの入力xに対し、N-1=p(n)ステップで問題Pの答P(x)=yes/noを(例えば)最初のセルに書き込んで停止する
M_Pの入力xに対する動作列を記述し答がyesかnoかを判定する論理式L(x)をNの多項式時間で作り、L(x)が充足可能⇔P(x)=yes となるようにする

変数	=真の意味	個数
S_tq	時点tのM_Pのプログラム命令（内部状態）がq	N×命令（状態）数
T_tja	時点tのメモリ（テープセル）jの内容が記号a	N²×記号数
H_tk	時点tのアクセスメモリ番地（ヘッド位置）がk	N²

注．プログラム（チューリング機械）がアクセスできるメモリ（セル）数≦N

これらの変数に対する真偽の割り当てが、M_Pの正しい計算になって(動作規則を満たして)いて出力がyesのときにのみ真となるような論理式をつくればよい。

NP完全問題の例

充足性判定問題
ハミルトン(閉)路問題：与えれれたグラフがハミルトン(閉)路を持つか
巡回セールスマン問題：与えれた都市をすべてめぐるコストw以下の路があるか
3彩色問題：与えれたグラフの頂点を3色で塗り分けることができるか

P問題ではなさそうなNP問題
素因数分解：与えられた数の素因数分解を求める
（素数判定は最近P問題であることが示された）

公開鍵暗号

送信者　　　　通信路　　受信者
平文[暗号化]⇒　暗号　⇒[復号]平文　

共通鍵暗号：送信者と受信者で実質的に同じ鍵を用いる
　鍵(と手順)を秘密裡に共有し(ネット上で可能？)
　送られた暗号をその鍵で復号
　例 IBM[1文字前]⇒ HAL ⇒[1文字後]IBM

公開鍵暗号：送信者(暗号化)と受信者(復号)で異なる鍵
　受信者が暗号化の鍵(と手順)を公開
　送られた暗号を秘密にしている鍵で復号
　公開(暗号化)鍵から秘密(復号)鍵が分からないのか？
　　　RSA暗号、楕円曲線暗号

パズル．通信路の盗聴者が、公開鍵暗号を破るための方法を考えよ。

RSA公開鍵暗号の作成実験

p,qが素数⇒x＝x^1+(p-1)(q-1) (mod pq)
x＝x^1+(p-1)(q-1)＝x^{1+2(p-1)(q-1)}＝… (mod pq)なので、
de＝1 (mod(p-1)(q-1))なら(x^d)^e＝(x^e)^d＝x^de＝x(mod pq)。
n=pqを法としたd乗とe乗が互いに逆関数⇒暗号化と復号に利用

公開鍵：nとe　　　　秘密鍵：nとd（とp, q）

RSA暗号の安全性

　RSA暗号を破るには、次のような方法が考えられる。

暗号(の値)を、nを法として1乗、2乗、3乗、…して元に戻るか否かで調べる。d 乗まで調べた時点で元に戻るから、秘密鍵 d をいつかは知ることができる。
nの約数p(q)を探し、(p-1)(q-1)を法とする(1÷e)を計算してdを求める。
推測した平文(の一部)xをmod nでe乗して盗聴した暗号(の一部)yと一致するか見る。

　これらはいずれも虱潰しの方法で、素朴ベキ乗計算の実習でみたように、nの値や秘密鍵、素数p、qを十分おおきくとれば、現実的ではない。また、与えられた x，y，n，に対し、x＝y^d (mod n) を満たすdを求める効率的な方法は知られていないし、nからp, qを求める効率的な因数分解の方法も知られていない。したがって、安全と考えてよい。

　ところで、x^dの計算は復号計算でもあるから、その計算に x を(d-1)回掛ける素朴な方法しかなければ、復号にとんでもない時間がかかってしまうことになり、RSA暗号は機能しない。幸い、d の値がわかっていれば、d 乗を高速に行うBinary法が知られている。

RSA暗号の安全性とP≠NP

　前ページでは、復号は、秘密鍵 dを知っている本人は高速実行できるが、たとえ暗号を入手(盗聴)できたとしても、秘密鍵を知らない第3者が可能な素朴な方法では、現実的な時間内に実行できないことがわかった。
　現在のところRSA暗号を現実的な時間内に破る方法は知られていないが、何か巧妙な方法が、まだ見つかっていないだけで、今後見つかる可能性が0とは決まっていない。そのような方法は存在しえず、それゆえRSA暗号は安全であると広く信じられてはいるが、そのことの数学的に厳密な証明は得られていない。
　これは、今回紹介したP≠NP問題というクレイ数学研究所から100万ドルの賞金がかけられている有名な未解決問題に、密接に関係する問題である。

電子署名

署名＝文書を秘密鍵で暗号化したもの
文書＋署名の受取人は公開鍵で署名を復号して文書との一致を検証する

公開鍵で復号できる暗号を作れるのは秘密鍵の持ち主だけ
⇒文書の改ざん、署名の偽造(なりすまし)が防げる

電子署名はゼロ知識証明
　秘密(鍵)を明かすことなく、秘密(鍵)を知っていることを証明する（納得させる）

マジックプロトコル

コイントス：A,B 両者が信頼できる第三者を介さずに通信線上で行う
　コインを投げるAは、Bの答を聞いた後でコインの裏表を変えられない
　裏表を当てるBは、Aが投げたコインを盗み見できない
　Bが答えた後、その当否を両者(特にB)が確認できる

プロトコル(通信手順)

Aは乱数rをBに送り、rのAによる署名の偶奇をBに問う。
Bは偶奇を答える。
Aはrの署名をBに送り、Bはそれを検証する

パズル．上のプロトコルがうまく働くことを示せ。

他のマジックプロトコル：いずれも通信線で第三者を介さずに行う
金持ち比べ：互いの資産額を知らせずに、その大小を比べる
カード配り：トランプのカードを配る
電子投票：投票の秘密を保って投・開票を行う

アルゴリズムの考え方：現実的計算可能性