「難問「ＡＢＣ予想」解明か」記事へのコメント

物質材料系、IT系、法律系の優れた人はスラドにいるけど

[Anonymous Coward]

数学系はいるのかな？
http://ja.wikipedia.org/wiki/ABC%E4%BA%88%E6%83%B3 [wikipedia.org]
を見る限り予想の内容は理解できるが、応用とか証明とかさっぱり・・・

昨日の日刊スポーツの記事の方が、今日の読売より分かりやすい記事だ。
・「ＡＢＣ予想」は、整数の方程式の解析では「最も重要な未解決の問題」
・まだほとんどの数学者が理解できていないような新たな数学的手法を開発し、駆使して証明。
・（上記数学的手法は）この予想以外の整数論の問題を解く強力な道具になるとも期待
http://www.nikkansports.com/general/news/f-gn-tp0-20120918-1019282.html [nikkansports.com]

御尊顔
＞平成４年に２３歳で京都大助手に就任した際は日本語が

Re:

[Anonymous Coward]

P≠NP予想 [wikipedia.org]が証明されたら /. でも大きな話題になりそうですけどねぇ

# カップ的にはC（略

Re:

[kurema (42872)]

P≠NPだと証明されれば、みんなフーンやっぱりそうだったんだという事で、量子計算機が普及するまでのわずかな時間・そして量子計算機では解けない暗号化を使い安心していられるでしょう。
P=NPだと証明されれば、そうでなくとも人間より低コストにほとんどの問題が解決できるという事になれば、/.どころではなく世界は大騒ぎです。
既存の暗号が使えなくなるなんてのはどうでもいい話です。どうせ普通の暗号は十年ももちませんし。郵送式のワンタイムパッドが普及すればいい。

こんな事が起きます。

• どんな正しい予想もコンピュータで数秒で証明できるよう

Re:

[fareast (45345)]

すごく興味深い。けど知識が追いつかないので、一般人の目線から訊いてみたい。
P=NP のアルゴリズムって、非決定的な多項式時間の問題を決定的な多項式時間の問題に自動的に置き換えるアルゴリズムってことでいいのかな。

P=NP が証明されたと仮定して、現状のコンピュータの計算能力でたいていの問題を解けるアルゴリズムが、現実に開発できる？
いくら多項式時間といっても、ある問題では現在のコンピュータで何万年という時間がかかる、ということにならないとも限らないと思うし。

それと、どんな問題でも指数関数時間の解法ならごく簡単に見つかる、ということでいいのかな。
また、定理の証明が全自動でできるようになったとして、予想も自動でできるもの？
そうでなければ数学者の仕事はまだ残っているということになるような。

Re:物質材料系、IT系、法律系の優れた人はスラドにいるけど

[kurema (42872)]

私も一般人なので詳しくは偉い人にお願いします。

P=NPを証明するアルゴリズムが現実に解けるレベルになるかは全く予想できません。
Pクラスでも難しい問題があるとは思いますが、とにかくPクラスになるというだけです。

それとどんな問題でも解けるという事ではありません。
よく誤解されますが、NPはPより難しい問題全てではなく

• yesの証拠を多項式時間で検証できる問題
• 一サイクルごとに自己分裂する気持ち悪いコンピューターで多項式時間で解ける問題

(互いに同値)の事でPクラスを含みます。
量子コンピューターの偉い人なんかも勘違いしているのを見ました。

世の中にはNPクラスより難しい問題があって、NP困難と呼ばれます。
巡回セールスマン問題やそもそも一般には解けない停止問題やビジービーバー関数なんかを含みます。
ややこしいですがこれはNP問題に含まれません。

また、予想はNP問題が解けても可能にはなりません。
しかし帰納法や問題の変形なんかはP問題に属しますから、AIが普通に進歩すればそのうちできるようになるでしょう。

Re:

[Anonymous Coward]

>また、予想はNP問題が解けても可能にはなりません。
>しかし帰納法や問題の変形なんかはP問題に属しますから、AIが普通に進歩すればそのうちできるようになるでしょう。

あなたがまったく数学を理解してないことは、この2文から明らかですね。