回答受付中の質問

素因数分解はＮＰ完全問題でしょうか？

emperor3322さん

素因数分解はＮＰ完全問題でしょうか？

それとも，クラスＮＰに属するだけでしょうか？？？

違反報告

質問日時：

2009/11/27 17:28:32
残り時間：

7日間
回答数：

2
お礼：

知恵コイン

100枚
閲覧数：

31
ソーシャルブックマークへ投稿：

Yahoo!ブックマークへ投稿

はてなブックマークへ投稿

（ソーシャルブックマークとは）

この質問に回答する

回答: （2件中1〜2件）

並べ替え：回答日時の: 新しい順; ｜; 古い順

shentechsさん

それは未解決問題です。
Wikipedia には
http://en.wikipedia.org/wiki/Integer_factorization
自然数の素因数分解は
P 問題でも NP 完全問題でもないと予想されている
と書いてあります。

現在、NP 完全問題には指数時間で解くアルゴリズムしか見つかっておらず、
素因数分解には準指数時間で解けるアルゴリズムがありますが、
多項式時間で解けるアルゴリズムが見つかっていません。
なので、私も自然数の素因数分解は
P 問題でも NP 完全問題でもないと思います。

違反報告
編集日時：2009/11/27 20:55:48
回答日時：2009/11/27 20:42:55

realhumen18さん

私はまったくわからないのですが、

素因数分解はＮＰ完全問題ではないとおもいます。

http://www.msc.cs.gunma-u.ac.jp/~nakano/Algo/npc.html

には

＞もしNP完全に属する問題のひとつが、多項式時間で解けたら、クラスNPに属する
＞問題は全て多項式時間で解ける。すなわちP=NPとなる。(のだけど、1971年以来
＞世界中の研究者がトライしても、未解決なので、P≠NPだと予想されている。)

と書かれているので

素因数分解は多項式時間で解ける問題なので
素因数分解がＮＰ完全ならばクラスNPに属する
問題は全て多項式時間で解ける。すなわちP=NPとなる。
ゆえにP≠NP予想は偽と簡単に証明できてしまう。

そんなことを数学者が気づかないわけないので、
素因数分解は素因数分解はＮＰ完全ではない。

違反報告
回答日時：2009/11/27 20:12:48

この質問に回答する

話題のキーワード

[カテゴリ：数学]