笑わない数学 #4（第4回） 8月3日放送分 『PVSNP問題』

PVSNP問題。PとはPolynomial time（多項式時間：ほどほどの時間）の略、NPとはNon-daterministic Polynomial time（非認定性多項式時間：しらみつぶしに解かないほど面倒な問題）。そのPとNＰがイコールかどうなのかという問題のようです。

つまり全ての問題が簡単に解けるかどうかということ。一筆書きできるかどうかというのなどがＰ問題となるようです。一筆書きは、点から伸びる線の数が偶数だと可能で、全て偶数じゃなくても奇数の点は2つ以下なら可能なようですね。

全ての問題が簡単に解けるのはいいことばかりではなく、悪意があった場合に大変なことが起きるという話が出ていました。それに何でも簡単に解けてもつまらないですよね。それこそ深く物事を考えない人だらけになりそうだなと思いました。