0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

P#NP予想からAI,機械学習の実装の方向性を考える

Posted at

実例

VSCodeにChatGPTの拡張機能を入れてコードレビューやバグを発見してもらう
https://qiita.com/tak001/items/c3000b3ce9b6e72b2ae5

P≠NPとは

https://ja.wikipedia.org/wiki/P%E2%89%A0NP%E4%BA%88%E6%83%B3
  クラスPとクラスNPが等しくなる例は存在しない
  これは証明自体は非常に困難でミレニアム懸賞問題になっています。ただし、この予想自体は正しいということは直感的には。。。わからないですね。

【ミレニアム懸賞問題】解けたら1億円!数学最大の難問「P≠NP予想」【ゆっくり解説】

  この動画の説明に曰く(というか確かにそうだ)$P≠NP$予想とは「ある問題の答え合わせより、答えを求めるほうが難しい」という予想だといえる。

ChatGPTの実装の記事はこの予想とどうかかわるのか

  つまり、問題を解く、というところを「コードを書く」と言い換える。そして、答え合わせを「コードレビューやバグを発見する」とすると、コードを書くより、コードをチェックさせたほうがAI自体もうまく動くだろうといえることになる。コードレビューやバグの評価はYes/Noで答えてもよく、Yes-No問題といえるからだ。そうすると計算複雑性はードチェックのほうが多項式時間で可能となるだろう。速度も速く、間違える可能性も低くなるからだ。もしP=NPであり、コードを書くのとコードのチェックの計算複雑性が同じであり、多項式時間で解決可能なら、コードを書かせる実装とコードレビューをさせる実装がQiitaに同時に記事が出現し、同等に動くということになる。
  しかし、こうはならない、ならないのは$P≠NP$予想が正しいであろうからだ。
  以上から、今回の記事のようなAI,機械学習の使い方、実装は最適であると判断される。

NPであるがPではない、あるいはPであるか不明という方向から

  上記動画で箱詰め問題が紹介されている。つまり効率的なものは(多項式時間では解決が)難しいが、効率的であるかどうかはチェック、レビューするほうは多項式時間で解決可能であることが多いといえる。
  このことからも一般的にAIや機械学習は何かを生み出すのではなく結果を評価、検証させるほうが向いているという予想が成立する。

P=NPは正しいか

  少数ながらこのように予想している人たちもいるという。これは解釈によっては正しいであろう。なぜなら$P≠NP$が「正しそう」なのは「答え合わせ」という表現のイメージにあらかじめ答えを知っているという前提があるからだ。しかし答え合わせをするとき、もう一度計算しなおしている場合には、答えを求めているのと変わらないケースが存在する。したがってP≠NP予想が正しくても、現実にはPなのかNPなのかはあいまいな場合があることから、同時にP=NPも成立するだろう。つまり、一般的にはP≠NPは正しいが、場合によっては$P=NP$も成立する。この予想が証明された場合、このような結果になるだろう。
  そうると、ChatGPTのようなAIや機械学習は必ずしも検証、レビューに向かない場合が存在し、それは答えを求めているのと変わらないか、厳密過ぎて計算量が増える場合(いわゆるNP困難)だと予想できる。
  また、現実には1つの関数を作動させると100時間もかかるようでは誰も使わない。現実のユーザーは時間と投資(お金)に見合うスピード、効率の上昇も求めているからだ。

そうするとどうなるか

  $P≠NP$予想が正しいとすれば、この例のようにAIや機械学習でチェックやレビューに関する機能を開発、実装をしていくことが開発可能であり、開発速度が速く、動作速度が速く、実用的かつ効率的な使用方法となるだろう。引用記事がその最適な例といえる。ただし計算量や複雑さによって$P=NP$となる場合があり、この場合はAIや機械学習もあまり有効ではない。またユーザーの要求にこたえるものでなければ、予想に限らず適切な使用方法とはならない。

参考文献

NP問題、あるいはNP困難問題

うさぎでもわかるP vs NP問題(NP完全、NP困難の違い)

クラスPとは、多項式時間以内で解くことができるアルゴリズムが存在するような問題のことを表します。
クラスNPは、多項式時間以内で、問題の解が本当に合っているかの検証を判定することができる問題のことを表します。

計算の複雑さと N P-完全問題

少なくとも NP-完全以上の難しさを持つ問題を NP-困難 (NP-hard) と呼ぶ。正確には、$P=NP$ でない限り、多項式時間のアルゴリズムが存在しないような問題で、NP に属するか否か問わないとき、NP-困難な問題であるという。

ビンパッキング問題(動画の箱詰め問題)

三彩色問題

グラフ彩色
https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%BD%A9%E8%89%B2
3-彩色問題
http://www.r.dendai.ac.jp/~nakano/shoutestkaitou/Sotsukenslide.pdf
3-彩色問題は上記サイトでもアルゴリズムと関係があり、また、下記サイトのとおり、本人認証とも関係がある。
https://www.omoshiro-suugaku.com/entry/3saishokumonndai-honnninnkakuninn

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?