P vs NP

0001１３２人目の素数さん

2012/08/13(月) 06:56:27.00

http://en.wikipedia.org/wiki/P_versus_NP_problem

2012/08/13(月) 06:57:57.40

描

>14 名前：１３２人目の素数さん：2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間｡
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>

0003１３２人目の素数さん

2012/08/13(月) 07:30:49.08

> 363 自分：１３２人目の素数さん[sage] 投稿日：2012/08/12(日) 21:39:21.60
> 質問です
> 例えば群であれば、ある位数nの群すべてを多項式時間で見つけ出す
> アルゴリズムは存在しているといえるのですか？
>
> 364 名前：１３２人目の素数さん[sage] 投稿日：2012/08/12(日) 22:33:17.37
> nが2のべきの時に位数nの群の同型類の個数はやたら大きくなるから
> そもそも個数自体が多項式で抑えられるか疑問だと思う
> たぶん無理
>
> 位数256の群は56,092個
> 位数512の群は10,494,213個
> 位数1024の群は49,487,365,422個
>
> http://www.icm.tu-bs.de/ag_algebra/software/small/number.html

0004baka描 ◆ghclfYsc82

2012/08/13(月) 07:38:30.85

描

>14 名前：１３２人目の素数さん：2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間｡
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>

0005１３２人目の素数さん

2012/08/13(月) 10:04:29.12

　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　／:::::; -‐''"　　　　　　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　　　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　　　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　　ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　　　 | 　　　　 ` -'＼　　　　　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　　＿＿／　ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　　 |　　　　　　　（:::::`‐-､__ 　|::::`､　　ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼　 |　'､　　＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/

0006浩二ート ◆ghclfYsc82

2012/08/13(月) 11:12:55.53

ふむ、見たところnが2倍になるごとにケタが3つ上がっとるだけやナ
これやったらn^11で足りるナ

0007baka描 ◆ghclfYsc82

2012/08/13(月) 12:08:08.63

描

>14 名前：１３２人目の素数さん：2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間｡
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>

0008１３２人目の素数さん

2012/08/13(月) 16:20:25.84

　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　／:::::; -‐''"　　　　　　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　　　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　　　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　　ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　　　 | 　　　　 ` -'＼　　　　　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　　＿＿／　ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　　 |　　　　　　　（:::::`‐-､__ 　|::::`､　　ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼　 |　'､　　＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

0009１３２人目の素数さん

2012/08/18(土) 11:24:07.84

過疎ってるようなので質問お願いします
群の定義は「演算が閉じること」「結合則が成り立つこと」「どの元にも逆元が
存在すること」「単位元が存在すること」の４つですが、単純群の分類理論を
用いずに、この定義だけからある位数nの群全てを見つけようとするとそれは
NPになってしまう、という理解は正しいですか？

単位元を用意して、逆元とペアになった２つの元か自分自身が逆元である１つの
元を順次加えていっても結合則の保証や演算が閉じることの保証はできません。
もし演算が閉じることや結合則が必要なければPで解くことができて、演算が閉じる
ことや結合則のような集合に対する「縛り」でしかないものを解こうとするとNPに
なってしまう、という理解で正しいでしょうか？

ご指導お願いします

0010１３２人目の素数さん

2012/08/18(土) 17:28:18.89

nが与えられたときに具体的にどういう出力を返す問題の事を言っているのか分からない。
それぞれの群ごとにn^2の演算表を全部出力するの？
それとも例えば生成元と基本関係式で答えたり行列を用いて表現したりするの？

いずれにせよ、NPというのはyesかnoで応えられるような問題で、
しかも答えが実際に与えられたときに、その答えが本当に正しいかどうかを
多項式時間で判定できるような問題だということなんだけど、
たぶんあなたの考えているような問題はNPですらないんじゃないだろうか。
まずはPとNPの定義くらい確認したらどうだろう

0011１３２人目の素数さん

2012/08/18(土) 20:15:54.28

むしろDTMとNTMの定義を読んでこういうことかな？と思って質問したのですが．．．
得られる結果をどういうデータ構造で格納するかによって問題の種類が変わりますか？
欲しい出力は与えられた位数nの群全てを何らかのデータ構造で格納したものです

0012１３２人目の素数さん

2012/08/18(土) 21:37:30.78

演算表で出力するなら
位数nの群m個を表示するのにn^2mの長さの出力が要るじゃん

他のNP問題でそんなバカでかい出力を要する問題見たことないよ
というかそれ以前にNPもPもyes/noで応えられる決定問題のクラスらしいよ

0013１３２人目の素数さん

2012/08/18(土) 22:13:07.17

yes/noで答えるために何をしなければならないか、あるいはどんなマシンでないと
多項式時間で解けないか、ですよね？

0014１３２人目の素数さん

2012/08/19(日) 12:37:18.55

>>12
なんなら出力は群の個数にします？

0015１３２人目の素数さん

2012/09/01(土) 21:26:21.37

おやすみー

0016１３２人目の素数さん

2012/09/14(金) 17:08:25.72

うざ

0017１３２人目の素数さん

2012/09/27(木) 13:33:16.40

そそるな

0018１３２人目の素数さん

2012/10/08(月) 12:50:48.58

　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　／:::::; -‐''"　　　　　　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　　　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　　　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　　ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　　　 | 　　　　 ` -'＼　　　　　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　　＿＿／　ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　　 |　　　　　　　（:::::`‐-､__ 　|::::`､　　ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼　 |　'､　　＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

0019１３２人目の素数さん

2012/10/14(日) 10:08:06.37

　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　／:::::; -‐''"　　　　　　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　　　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　　　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　　ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　　　 | 　　　　 ` -'＼　　　　　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　　＿＿／　ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　　 |　　　　　　　（:::::`‐-､__ 　|::::`､　　ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼　 |　'､　　＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/

0020１３２人目の素数さん

2012/10/14(日) 22:07:54.00

私はP=NPだと考えています。

0021南沢木綿子 ◆1Tm7DPhqbVXq

2012/10/23(火) 12:59:51.31

　　∧,,,∧　
　( 　・∀・)　ほー　それで
　 (　　：　)　
　　し─J

0022馬と鹿と豚さん

2012/10/24(水) 23:08:56.58

　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　／:::::; -‐''"　　　　　　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　　　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　　　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　
.　　　　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　このスレ、レス数がやや少ないので上げとくわね。
　　　　 | 　　　　l＾,人| 　` `-' 　　ゝ　 |　　　　　　　　
　　　 | 　　　　 ` -'＼　　　　　ｰ' 　人　　　　　　　　　　
　　　　|　　　　　　　 /(l 　　　＿＿／　ヽ、　　　　　　　　　　　
　　　 |　　　　　　　（:::::`‐-､__ 　|::::`､　　ﾋﾆﾆヽ、　　　　　　　　　
　　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼　 |　'､　　＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

0023１３２人目の素数さん

2012/10/25(木) 02:01:53.21

NP困難問題である巡回セールスマン問題は多項式時間で解けそうだ。

0024１３２人目の素数さん

2012/11/08(木) 18:16:41.88

　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　／:::::; -‐''"　　　　　　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　　　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　　　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　　ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　　　 | 　　　　 ` -'＼　　　　　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　　＿＿／　ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　　 |　　　　　　　（:::::`‐-､__ 　|::::`､　　ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼　 |　'､　　＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

0025令嬢

2012/12/20(木) 19:46:18.56

　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　／:::::; -‐''"　　　　　　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　　　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　　　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　　ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　　　 | 　　　　 ` -'＼　　　　　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　　＿＿／　ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　　 |　　　　　　　（:::::`‐-､__ 　|::::`､　　ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼　 |　'､　　＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

0026１３２人目の素数さん

2013/01/19(土) 20:13:29.49

　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　／:::::; -‐''"　　　　　　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　　　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　　　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　
.　　　　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　
　　　　 | 　　　　l＾,人| 　` `-' 　　ゝ　 |　　　　　　　　このスレは馬と鹿と豚さんばかりね。
　　　 | 　　　　 ` -'＼　　　　　ｰ' 　人　　　　　　　　　　　　
　　　　|　　　　　　　 /(l 　　　＿＿／　ヽ、　　　　　　　　　　
　　　 |　　　　　　　（:::::`‐-､__ 　|::::`､　　ﾋﾆﾆヽ、　　　　　　　　　
　　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼　 |　'､　　＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

0027１３２人目の素数さん

2013/02/12(火) 01:42:53.60

　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　／:::::; -‐''"　　　　　　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　　　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　　　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　
.　　　　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　
　　　　 | 　　　　l＾,人| 　` `-' 　　ゝ　 |　　　　　　　　このスレには馬と鹿と豚さんしかいないのね。
　　　 | 　　　　 ` -'＼　　　　　ｰ' 　人　　　　　　　　　　　　
　　　　|　　　　　　　 /(l 　　　＿＿／　ヽ、　　　　　　　　　　
　　　 |　　　　　　　（:::::`‐-､__ 　|::::`､　　ﾋﾆﾆヽ、　　　　　　　　　
　　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼　 |　'､　　＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

0028１３２人目の素数さん

2013/04/22(月) 14:22:42.66

NP=PならP=NP=NP=P とならないならP=NPとはならない
ﾐﾚﾆｱﾑ問題の1つ解決

0029１３２人目の素数さん

2013/04/22(月) 16:31:43.01

>>28
1*2=2
2=1*2=1*2=2
というP=NPならP vs NPは否定される

0030１３２人目の素数さん

2013/04/22(月) 16:36:10.72

>>29
Nを1の集合Pは2の集合とすると
2に1を幾らかけ算しても2
2進法か3進法ならP vs NPは否定される

0031１３２人目の素数さん

2013/08/17(土) NY:AN:NY.AN

p

0032１３２人目の素数さん

2013/09/04(水) 02:41:42.48

このスレの人なら知っているかもしれないんで聞きます。
山口人生博士って、どうやって生計を立てているんですか。

0033 忍法帖【Lv=34,xxxPT】(1+0：8)

2014/01/10(金) 11:02:20.37

>>1
これ問題自体がおかしいだろ

そもそも
より計算量の少ないアルゴリズムが存在したところで
そのアルゴリズムを見つけるために要した時間は
どこに消えちゃうのさ？

さらに、存在しないなんてのを見つけろなんて言う問題は
悪魔の証明だよ？

0034１３２人目の素数さん

2014/01/11(土) 14:42:12.66

低レベルなレスばかりだな。
P vs NP問題の定義が分かっていれば、出て来ないような意見ばかりだ。
アホ過ぎ。

0035 忍法帖【Lv=37,xxxPT】(1+0：8)

2014/01/12(日) 13:32:23.81

多項式時間以内に収まる最短経路が存在するかどうかの問題

何かの数学上の系において
ある問題＝拘束条件を与えた時
多項式時間以内に収まるアルゴリズムが存在する場合に
その出力が問題の解に含まれるかを確認できる
多項式時間以内に収まる経路が存在するかどうか

系が与える前提あるいはルールと問題が与える拘束条件
さらにこれらが生成するさまざまな経路が存在し得るんだけど
一番短い経路は多項式時間以内に収まりますか？
最悪集合全部を読み上げてそれに含まれるかを調べればよい

だが系の定義によって同値ではなく一方向や非可逆な経路とかもあって
その場合は最初からすべて生成してみないことにはわからないことがある
あるいは別経路で到達可能かを探さないといけないわけだが
それはそれで総当り戦になるし、そういう経路がいくつあるのかも
生成して読みあげてみないとわからない

人間が試してたまたまうまくいくのを探し当てられたらそれはＰ＝ＮＰ問題

んで、すべてのＰ問題についてさらにこれら上記をもう一度やるという問題

すべてのＰ問題を生成しなくても何らかの別経路で証明＝到達出来ればよいが・・・
それには問題を再定義しないといけないな

最悪多項式時間以内に収まるＰアルゴリズムが存在する問題の集合をすべて生成してもいいけどさｗそれって多項式時間以内に収まるか？という再帰問題になるぜ？ｗ

0036１３２人目の素数さん

2014/03/05(水) 13:01:23.82

>>33
より計算量の少ないアルゴリズムが存在したらそれはええことやないか。それともあかんのか

0037１３２人目の素数さん

2014/03/05(水) 22:13:39.77

一次従属とかを直接扱えるCPUがあったらぜひプログラミングしてみたい

0038１３２人目の素数さん

2014/03/23(日) 12:49:49.80

P vs NP問題を解決するとされている、「消滅解」って、
具体的にどういうものか知っている人いますか。

0039１３２人目の素数さん

2014/03/23(日) 13:24:28.54

玉石混淆スレあげ

0040１３２人目の素数さん

2014/03/23(日) 13:51:31.59

平叙文と命令文が等価ならプログラマ全員失業やがな

0041１３２人目の素数さん

2014/03/24(月) 04:34:23.24

山口人生氏の本を読んだけど、本に記されている記述が不十分なのか、私の理解力が不十分なのか分りませんが、
読んでも結局分りませんでした。

0042１３２人目の素数さん

2014/03/24(月) 18:46:51.48

分かったら数学続けられんよ

0043１３２人目の素数さん

2014/05/16(金) 00:49:05.73

PvsNPってイエスかノーで答えられる判定問題だけを扱うんだよね
P=NPだとしたらRSA暗号が簡単に解読できる方法があることになるからヤバいって話をよく聞くけど、ある数の素因数を求めよって問題は判定問題じゃないから、PやNPとは何も関係ないんじゃね？

0044１３２人目の素数さん

2014/05/21(水) 19:53:56.05

>>43
NがM未満の素因数を持つか？っていう決定問題がPだと、二分探索をその桁数のオーダーだけやれば解けちゃうよ

0045１３２人目の素数さん

2014/05/21(水) 23:05:57.83

>>44

>>43だが納得しました