by ご近所のきよきよ

　前の随筆「P=?NP問題」を書いてから、少し考えてきました。2**nな問題で、NPがnの問題を作れれば、P!=NPがいえるのですよね。

　これって、折りたたみ的な問題だとおもうのです。NPに問題をもっていくというのは、問題を分断して見てくれを簡単にする手法の一つと考えるわけですね。未夢の曖昧性処理をやっていて苦悩しましたから、分断していってパスの長さをnにできたとして、問題はやっぱり2**nが保存されているのに気が付くことになったわけです。Pでない問題では決してPなステップのアルゴリズムが見いだされることはないと肌で感じるのです。

　「折りたたみ」といったのは、問題をパス長nにしたとき、各分断点は2**(n-1)な選択肢を持つことになります。どんな問題も任意に分断点を持つようにアルゴリズムを組めますから、Pでない問題もNPにすることはできるわけです。従って、P!=NP。

　ただし、選択肢の最大がたかだかPの時は、このNPはPになるといえるでしょう。n**2問題になるからです。

　この方針をテキスト処理に応用すれば、P!=NPな問題を簡単に組み立てることができるでしょう。つまり、記号列Ai(i=1・・・n)がそれぞれSij(i=1・・・n,j=・・・n)の曖昧性を持っている（選択肢を持っている）として、その中からもっともふさわしい意味が通る文を選ぶことです。明らかに問題はPではありません。ある選択をしたら、その残りの方に最適解があるとして、問題を設定すれば最低でもn**nの組み合わせを調べなくてはなりません。したがってPでない問題です。しかし、パスはｎですから、問題としてはNPです。

おわり