1１３２人目の素数さん2012/08/13(月) 06:56:27.00
2baka描 ◆ghclfYsc82 2012/08/13(月) 06:57:57.40
描
>14 名前：１３２人目の素数さん ：2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間｡
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>
3１３２人目の素数さん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 4baka描 ◆ghclfYsc82 2012/08/13(月) 07:38:30.85
描
>14 名前：１３２人目の素数さん ：2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間｡
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>
5１３２人目の素数さん2012/08/13(月) 10:04:29.12
__ﾉ)-'´￣￣`ｰ- ､_
, '´ _. -‐'''"二ニﾆ=-`ヽ、
／ ／:::::; -‐''" `ｰノ
/ ／:::::／ ＼
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ﾊ .| ,ﾊ|
| |/ / / /| ,ﾊﾉ| /|ﾉﾚ,ﾆ|ﾙ'
| | | / / ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/ 私は只の数ヲタなんかとは付き合わないわ。
. | ＼ ∠イ ,ｲイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l＾,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'＼ ｰ' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l ＿＿／ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| （:::::`‐-､__ |::::`､ ﾋﾆﾆヽ、 あなたの論文が Ann of Math に accept される確率は?
| ／ `‐-､::::::::::`‐-､::::＼ /,ﾆﾆ､＼ それとも最近は Inv. Math. の方が上かしら？
| |::::::::::::::::::|` -､:::::::,ﾍ￣|'､ ﾋﾆ二、 ＼
. | /::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ | '､ ＼
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ ヽ、 |
| |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ /:＼__/‐､
| |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::| く:::::::::::::￣|
| /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
| |／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
6浩二ート ◆ghclfYsc82 2012/08/13(月) 11:12:55.53
ふむ、見たところnが2倍になるごとにケタが3つ上がっとるだけやナ
これやったらn^11で足りるナ
7baka描 ◆ghclfYsc82 2012/08/13(月) 12:08:08.63
描
>14 名前：１３２人目の素数さん ：2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間｡
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>
8１３２人目の素数さん2012/08/13(月) 16:20:25.84
__ﾉ)-'´￣￣`ｰ- ､_
, '´ _. -‐'''"二ニﾆ=-`ヽ、
／ ／:::::; -‐''" `ｰノ
/ ／:::::／ ＼
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ﾊ .| ,ﾊ|
| |/ / / /| ,ﾊﾉ| /|ﾉﾚ,ﾆ|ﾙ'
| | | / / ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/ 私は只の数ヲタなんかとは付き合わないわ。
. | ＼ ∠イ ,ｲイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l＾,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'＼ ｰ' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l ＿＿／ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| （:::::`‐-､__ |::::`､ ﾋﾆﾆヽ、 あなたの論文が Ann of Math に accept される確率は?
| ／ `‐-､::::::::::`‐-､::::＼ /,ﾆﾆ､＼ それとも最近は Inv. Math. の方が上かしら？
| |::::::::::::::::::|` -､:::::::,ﾍ￣|'､ ﾋﾆ二、 ＼
. | /::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ | '､ ＼
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ ヽ、 |
| |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ /:＼__/‐､
| |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::| く:::::::::::::￣|
| /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
| |／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/
9１３２人目の素数さん2012/08/18(土) 11:24:07.84
過疎ってるようなので質問お願いします
群の定義は「演算が閉じること」「結合則が成り立つこと」「どの元にも逆元が
存在すること」「単位元が存在すること」の４つですが、単純群の分類理論を
用いずに、この定義だけからある位数nの群全てを見つけようとするとそれは
NPになってしまう、という理解は正しいですか？
単位元を用意して、逆元とペアになった２つの元か自分自身が逆元である１つの
元を順次加えていっても結合則の保証や演算が閉じることの保証はできません。
もし演算が閉じることや結合則が必要なければPで解くことができて、演算が閉じる
ことや結合則のような集合に対する「縛り」でしかないものを解こうとするとNPに
なってしまう、という理解で正しいでしょうか？
ご指導お願いします
10１３２人目の素数さん2012/08/18(土) 17:28:18.89
nが与えられたときに具体的にどういう出力を返す問題の事を言っているのか分からない。
それぞれの群ごとにn^2の演算表を全部出力するの？
それとも例えば生成元と基本関係式で答えたり行列を用いて表現したりするの？
いずれにせよ、NPというのはyesかnoで応えられるような問題で、
しかも答えが実際に与えられたときに、その答えが本当に正しいかどうかを
多項式時間で判定できるような問題だということなんだけど、
たぶんあなたの考えているような問題はNPですらないんじゃないだろうか。
まずはPとNPの定義くらい確認したらどうだろう
11１３２人目の素数さん2012/08/18(土) 20:15:54.28
むしろDTMとNTMの定義を読んでこういうことかな？と思って質問したのですが．．．
得られる結果をどういうデータ構造で格納するかによって問題の種類が変わりますか？
欲しい出力は与えられた位数nの群全てを何らかのデータ構造で格納したものです
12１３２人目の素数さん2012/08/18(土) 21:37:30.78
演算表で出力するなら
位数nの群m個を表示するのにn^2mの長さの出力が要るじゃん
他のNP問題でそんなバカでかい出力を要する問題見たことないよ
というかそれ以前にNPもPもyes/noで応えられる決定問題のクラスらしいよ
13１３２人目の素数さん2012/08/18(土) 22:13:07.17
yes/noで答えるために何をしなければならないか、あるいはどんなマシンでないと
多項式時間で解けないか、ですよね？
14１３２人目の素数さん2012/08/19(日) 12:37:18.55
15１３２人目の素数さん2012/09/01(土) 21:26:21.37
おやすみー
16１３２人目の素数さん2012/09/14(金) 17:08:25.72
うざ
17１３２人目の素数さん2012/09/27(木) 13:33:16.40
そそるな
18１３２人目の素数さん2012/10/08(月) 12:50:48.58
__ﾉ)-'´￣￣`ｰ- ､_
, '´ _. -‐'''"二ニﾆ=-`ヽ、
／ ／:::::; -‐''" `ｰノ
/ ／:::::／ ＼
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ﾊ .| ,ﾊ|
| |/ / / /| ,ﾊﾉ| /|ﾉﾚ,ﾆ|ﾙ'
| | | / / ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/ 私は只の数ヲタなんかとは付き合わないわ。
. | ＼ ∠イ ,ｲイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l＾,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'＼ ｰ' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l ＿＿／ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| （:::::`‐-､__ |::::`､ ﾋﾆﾆヽ、 あなたの論文が Ann of Math に accept される確率は?
| ／ `‐-､::::::::::`‐-､::::＼ /,ﾆﾆ､＼ それとも最近は Inv. Math. の方が上かしら？
| |::::::::::::::::::|` -､:::::::,ﾍ￣|'､ ﾋﾆ二、 ＼
. | /::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ | '､ ＼
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ ヽ、 |
| |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ /:＼__/‐､
| |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::| く:::::::::::::￣|
| /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
| |／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/
19１３２人目の素数さん2012/10/14(日) 10:08:06.37
, '´ _. -‐'''"二ニﾆ=-`ヽ、
／ ／:::::; -‐''" `ｰノ
/ ／:::::／ ＼
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ﾊ .| ,ﾊ|
| |/ / / /| ,ﾊﾉ| /|ﾉﾚ,ﾆ|ﾙ'
| | | / / ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/ 私は只の数ヲタなんかとは付き合わないわ。
. | ＼ ∠イ ,ｲイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l＾,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'＼ ｰ' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l ＿＿／ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| （:::::`‐-､__ |::::`､ ﾋﾆﾆヽ、 あなたの論文が Ann of Math に accept される確率は?
| ／ `‐-､::::::::::`‐-､::::＼ /,ﾆﾆ､＼ それとも最近は Inv. Math. の方が上かしら？
| |::::::::::::::::::|` -､:::::::,ﾍ￣|'､ ﾋﾆ二、 ＼
. | /::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ | '､ ＼
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ ヽ、 |
| |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ /:＼__/‐､
| |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::| く:::::::::::::￣|
| /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
| |／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
20１３２人目の素数さん2012/10/14(日) 22:07:54.00
私はP=NPだと考えています。
21南沢木綿子 ◆1Tm7DPhqbVXq 2012/10/23(火) 12:59:51.31
∧,,,∧
( ・∀・) ほー それで
( ： )
し─J
22馬と鹿と豚さん2012/10/24(水) 23:08:56.58
__ﾉ)-'´￣￣`ｰ- ､_
, '´ _. -‐'''"二ニﾆ=-`ヽ、
／ ／:::::; -‐''" `ｰノ
/ ／:::::／ ＼
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ﾊ .| ,ﾊ|
| |/ / / /| ,ﾊﾉ| /|ﾉﾚ,ﾆ|ﾙ'
| | | / / ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/
. | ＼ ∠イ ,ｲイ| ,`-' | このスレ、レス数がやや少ないので上げとくわね。
| l＾,人| ` `-' ゝ |
| ` -'＼ ｰ' 人
| /(l ＿＿／ ヽ、
| （:::::`‐-､__ |::::`､ ﾋﾆﾆヽ、
| ／ `‐-､::::::::::`‐-､::::＼ /,ﾆﾆ､＼
| |::::::::::::::::::|` -､:::::::,ﾍ￣|'､ ﾋﾆ二、 ＼
. | /::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ | '､ ＼
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ ヽ、 |
| |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ /:＼__/‐､
| |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::| く:::::::::::::￣|
| /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
| |／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/
23１３２人目の素数さん2012/10/25(木) 02:01:53.21
NP困難問題である巡回セールスマン問題は多項式時間で解けそうだ。
24１３２人目の素数さん2012/11/08(木) 18:16:41.88
__ﾉ)-'´￣￣`ｰ- ､_
, '´ _. -‐'''"二ニﾆ=-`ヽ、
／ ／:::::; -‐''" `ｰノ
/ ／:::::／ ＼
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ﾊ .| ,ﾊ|
| |/ / / /| ,ﾊﾉ| /|ﾉﾚ,ﾆ|ﾙ'
| | | / / ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/ 私は只の数ヲタなんかとは付き合わないわ。
. | ＼ ∠イ ,ｲイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l＾,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'＼ ｰ' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l ＿＿／ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| （:::::`‐-､__ |::::`､ ﾋﾆﾆヽ、 あなたの論文が Ann of Math に accept される確率は?
| ／ `‐-､::::::::::`‐-､::::＼ /,ﾆﾆ､＼ それとも最近は Inv. Math. の方が上かしら？
| |::::::::::::::::::|` -､:::::::,ﾍ￣|'､ ﾋﾆ二、 ＼
. | /::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ | '､ ＼
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ ヽ、 |
| |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ /:＼__/‐､
| |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::| く:::::::::::::￣|
| /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
| |／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/
25令嬢2012/12/20(木) 19:46:18.56
__ﾉ)-'´￣￣`ｰ- ､_
, '´ _. -‐'''"二ニﾆ=-`ヽ、
／ ／:::::; -‐''" `ｰノ
/ ／:::::／ ＼
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ﾊ .| ,ﾊ|
| |/ / / /| ,ﾊﾉ| /|ﾉﾚ,ﾆ|ﾙ'
| | | / / ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/ 私は只の数ヲタなんかとは付き合わないわ。
. | ＼ ∠イ ,ｲイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l＾,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'＼ ｰ' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l ＿＿／ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| （:::::`‐-､__ |::::`､ ﾋﾆﾆヽ、 あなたの論文が Ann of Math に accept される確率は?
| ／ `‐-､::::::::::`‐-､::::＼ /,ﾆﾆ､＼ それとも最近は Inv. Math. の方が上かしら？
| |::::::::::::::::::|` -､:::::::,ﾍ￣|'､ ﾋﾆ二、 ＼
. | /::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ | '､ ＼
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ ヽ、 |
| |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ /:＼__/‐､
| |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::| く:::::::::::::￣|
| /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
| |／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/
26１３２人目の素数さん2013/01/19(土) 20:13:29.49
__ﾉ)-'´￣￣`ｰ- ､_
, '´ _. -‐'''"二ニﾆ=-`ヽ、
／ ／:::::; -‐''" `ｰノ
/ ／:::::／ ＼
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ﾊ .| ,ﾊ|
| |/ / / /| ,ﾊﾉ| /|ﾉﾚ,ﾆ|ﾙ'
| | | / / ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/
. | ＼ ∠イ ,ｲイ| ,`-' |
| l＾,人| ` `-' ゝ | このスレは馬と鹿と豚さんばかりね。
| ` -'＼ ｰ' 人
| /(l ＿＿／ ヽ、
| （:::::`‐-､__ |::::`､ ﾋﾆﾆヽ、
| ／ `‐-､::::::::::`‐-､::::＼ /,ﾆﾆ､＼
| |::::::::::::::::::|` -､:::::::,ﾍ￣|'､ ﾋﾆ二、 ＼
. | /::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ | '､ ＼
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ ヽ、 |
| |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ /:＼__/‐､
| |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::| く:::::::::::::￣|
| /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
| |／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/
27１３２人目の素数さん2013/02/12(火) 01:42:53.60
__ﾉ)-'´￣￣`ｰ- ､_
, '´ _. -‐'''"二ニﾆ=-`ヽ、
／ ／:::::; -‐''" `ｰノ
/ ／:::::／ ＼
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ﾊ .| ,ﾊ|
| |/ / / /| ,ﾊﾉ| /|ﾉﾚ,ﾆ|ﾙ'
| | | / / ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/
. | ＼ ∠イ ,ｲイ| ,`-' |
| l＾,人| ` `-' ゝ | このスレには馬と鹿と豚さんしかいないのね。
| ` -'＼ ｰ' 人
| /(l ＿＿／ ヽ、
| （:::::`‐-､__ |::::`､ ﾋﾆﾆヽ、
| ／ `‐-､::::::::::`‐-､::::＼ /,ﾆﾆ､＼
| |::::::::::::::::::|` -､:::::::,ﾍ￣|'､ ﾋﾆ二、 ＼
. | /::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ | '､ ＼
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ ヽ、 |
| |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ /:＼__/‐､
| |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::| く:::::::::::::￣|
| /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
| |／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/
28１３２人目の素数さん2013/04/22(月) 14:22:42.66
NP=PならP=NP=NP=P とならないならP=NPとはならない
ﾐﾚﾆｱﾑ問題の1つ解決
29１３２人目の素数さん2013/04/22(月) 16:31:43.01
>>28
1*2=2
2=1*2=1*2=2
というP=NPならP vs NPは否定される 30１３２人目の素数さん2013/04/22(月) 16:36:10.72
>>29
Nを1の集合Pは2の集合とすると
2に1を幾らかけ算しても2
2進法か3進法ならP vs NPは否定される 31１３２人目の素数さん2013/08/17(土) NY:AN:NY.AN
p
32１３２人目の素数さん2013/09/04(水) 02:41:42.48
このスレの人なら知っているかもしれないんで聞きます。
山口人生博士って、どうやって生計を立てているんですか。
33 忍法帖【Lv=34,xxxPT】(1+0：8) 2014/01/10(金) 11:02:20.37
>>1
これ問題自体がおかしいだろ
そもそも
より計算量の少ないアルゴリズムが存在したところで
そのアルゴリズムを見つけるために要した時間は
どこに消えちゃうのさ？
さらに、存在しないなんてのを見つけろなんて言う問題は
悪魔の証明だよ？ 34１３２人目の素数さん2014/01/11(土) 14:42:12.66
低レベルなレスばかりだな。
P vs NP問題の定義が分かっていれば、出て来ないような意見ばかりだ。
アホ過ぎ。
35 忍法帖【Lv=37,xxxPT】(1+0：8) 2014/01/12(日) 13:32:23.81
多項式時間以内に収まる最短経路が存在するかどうかの問題
何かの数学上の系において
ある問題＝拘束条件を与えた時
多項式時間以内に収まるアルゴリズムが存在する場合に
その出力が問題の解に含まれるかを確認できる
多項式時間以内に収まる経路が存在するかどうか
系が与える前提あるいはルールと問題が与える拘束条件
さらにこれらが生成するさまざまな経路が存在し得るんだけど
一番短い経路は多項式時間以内に収まりますか？
最悪集合全部を読み上げてそれに含まれるかを調べればよい
だが系の定義によって同値ではなく一方向や非可逆な経路とかもあって
その場合は最初からすべて生成してみないことにはわからないことがある
あるいは別経路で到達可能かを探さないといけないわけだが
それはそれで総当り戦になるし、そういう経路がいくつあるのかも
生成して読みあげてみないとわからない
人間が試してたまたまうまくいくのを探し当てられたらそれはＰ＝ＮＰ問題
んで、すべてのＰ問題についてさらにこれら上記をもう一度やるという問題
すべてのＰ問題を生成しなくても何らかの別経路で証明＝到達出来ればよいが・・・
それには問題を再定義しないといけないな
最悪多項式時間以内に収まるＰアルゴリズムが存在する問題の集合をすべて生成してもいいけどさｗ それって多項式時間以内に収まるか？という再帰問題になるぜ？ｗ
36１３２人目の素数さん2014/03/05(水) 13:01:23.82
>>33
より計算量の少ないアルゴリズムが存在したらそれはええことやないか。それともあかんのか 37１３２人目の素数さん2014/03/05(水) 22:13:39.77
一次従属とかを直接扱えるCPUがあったらぜひプログラミングしてみたい
38１３２人目の素数さん2014/03/23(日) 12:49:49.80
P vs NP問題を解決するとされている、「消滅解」って、
具体的にどういうものか知っている人いますか。
39１３２人目の素数さん2014/03/23(日) 13:24:28.54
玉石混淆スレあげ
40１３２人目の素数さん2014/03/23(日) 13:51:31.59
平叙文と命令文が等価ならプログラマ全員失業やがな
41１３２人目の素数さん2014/03/24(月) 04:34:23.24
山口人生氏の本を読んだけど、本に記されている記述が不十分なのか、私の理解力が不十分なのか分りませんが、
読んでも結局分りませんでした。
42１３２人目の素数さん2014/03/24(月) 18:46:51.48
分かったら数学続けられんよ
43１３２人目の素数さん2014/05/16(金) 00:49:05.73
PvsNPってイエスかノーで答えられる判定問題だけを扱うんだよね
P=NPだとしたらRSA暗号が簡単に解読できる方法があることになるからヤバいって話をよく聞くけど、ある数の素因数を求めよって問題は判定問題じゃないから、PやNPとは何も関係ないんじゃね？
44１３２人目の素数さん2014/05/21(水) 19:53:56.05
>>43
NがM未満の素因数を持つか？っていう決定問題がPだと、二分探索をその桁数のオーダーだけやれば解けちゃうよ 45１３２人目の素数さん2014/05/21(水) 23:05:57.83
46１３２人目の素数さん2014/08/06(水) 10:19:33.62
P/NP=N^(-1)
47１３２人目の素数さん2014/09/08(月) 01:06:52.16
みきやん予想
ある位数nの群全てを多項式時間で見つけ出すアルゴリズムは存在する
すみません、計算機屋のみきやんですけど反応ください
改定
みきやん予想
任意の位数nの群全てを多項式時間で見つけ出すアルゴリズムは存在する
P ≠ NP を自力で証明することと
P ≠ NP 予想を誰かが解決したあとにその照明の内容を理解することはどちらが難しいか？
入門書読むと、コンピュータ科学最大の難問の一つである、とか証明の努力を退けてきた、とか
いろいろ書いてあるけど、どういう試みがなされたのかとか証明につながるヒントとか
可能性がたかそうなルートとか研究の中途の説明ってないんだよねえ
誰か教えてよ
進展具合とか、もうみんな諦めちゃって手がついていないのか？
まあ、俺以外の誰かだと500年くらい掛かりそうだが、俺なら200年で出来る気がするな
人生短いから、実証出来ないのが残念
自力で証明する方が証明のチェックより難しいというのは
まさにP ≠ NP的な話だね
人工知能にNP問題学習させたら多項式時間で解けるようなったりして。
TSPの都市配置と最短経路を学習データとして
ディープラーニングで学習させたら良い解返してくれるんじゃないか。
>>63
わりといい近似解が出ることを、「とける」とは言わない CNFと充足解を学習データとして
ディープラーニングで学習させたらSATが多項式時間で解けるようになるかも
まあSATは無理でも素因数分解とかなら良い線いくんちゃう？
どうでもいい与太話も結構だが、君は「解ける」の意味をちゃんと理解してから書き込むように
導出原理なかなか楽しい。
鳩ノ巣原理なんかは時間かかるらしいが。
記述計算量において、
Pは「最小不動点演算子を持つ一階述語論理」で、
NPは「存在量化二階述語論理」であらわされる。
「最小不動点演算子を持つ一階述語論理」の無矛盾性を
「存在量化二階述語論理」で証明できれば、
ゲーデルの第二不完全性定理より、
「最小不動点演算子を持つ一階述語論理」より
「存在量化二階述語論理」が大きいと言えるから、
P≠NPも言えるのではないか。
この証明、どうだろう？
述語論理の公理系の規則が全てトートロジーである事から証明できると思います。
たとえばP vs NP が連続体仮説の結果に依存するとかいう可能性はあるの？
あるいはビジービーバーみたいにＮＰを多項式で解くアルゴリズムは存在することはするけど、
どのアルゴリズムがそれかは絶対わからないとか。
いきなりすまん。
解けたけど、(自分以外)だれも理解できないっぼい。
ペレルマンさんの気持ちがわかる気がする。
フィールズ賞もらえる歳は超えちまった。
ちなみに、フィールズ賞(ノーベル賞もだけど)は税金がかからんが、
クレイ研究所が提示してる方は免除の記載が無いらしいので、
このままだと半分が税金。
>>97-98
人生２世さん乙～ｗ （人生さんはあの第２巻は出さず終いなんだろうなあｗ）
P vs NP問題を解決した場合、もらえるのはフィールズ賞（純粋数学）じゃなくてネヴァンリンナ賞（理論計算機科学）だ
ちなみに年齢制限に関しては超えていても本当に解決したのならば特別賞が与えらえるだろうね
フェルマー大予想を解決したワイルズさんも（受賞時でなく）解決時に既に40歳の制限を超えていたがICM 1998でフィールズ賞の特別賞を受賞した
年齢制限はフィールズ賞を授与するICMの前年中に40歳に達していたらＮＧとのこと >>109
れすありがと。人生さんいたね。懐かしー
んで、ネヴァンリンナ賞なんですね。情報ありがとう。
ちなみに年齢制限は余裕で超えてるw 他の最近の研究動向調べてて思ったんだけど、この問題って、人気なさ気だなと。
しかも、一般的にも認知度が低い。リーマン問題さんがうらやましいww
>>111
知名度は低いかも知れませんけど
応用範囲の広さは随一でしょう
もっともP≠NPの可能性が高いですから
能率的なアルゴリズムが生まれるのではないですが
暗号の安全性という意味ではP≠NPが望ましい結果です NP完全問題をPで解けるアルゴリズムがある(だがその方法で最適解が求まる訳では無い)、とか、Pではあるんだが、O(n^10000) とかだったらどう？
>>133
前者は解けるとは言わない。近似解アルゴリズムならいくらでも手抜きできる
後者はそのままだと困難だけど改良の余地がある >>133 例えば背理法を用いて、P \neq NP を仮定して矛盾を示したとする。
(背理法で解けるという主張では無く、あくまで例です)
この時、存在は示されてたものの、
具体的に解を求めるアルゴリズムは示されて無いので、
実用性の面では役に立たない。
存在証明だけで凄い事ではあるんだろうけど。 >>133
SATだったら変数に真か偽か入れてはプログラムを動かせば、変数の数の回数だけ動かして、一つの解が求まる。
クソ遅い方はどうなんだろう。
素数判定は6乗位だったと思うけど実装されて、使われているのかな？ >>146
示されている方法でSATを解くと、
組み合わせ分を試すわけなので指数オーダーになるよ。
AKS素数判定法での計算量は (Wikiによると) \tild{O}(log(n)^7.5) っぽい。
でも、実際には使われてないだろうなー P≠NP問題は大多数の数学者が研究している現代数学の本流（代数、解析、幾何）からは遠く離れた辺境（計算機科学）で生まれた問題で
現在でも、研究が進んで道具立てが整備されている数学の本流とは結びついていないので難しい（難問に立ち向かうための道具が
貧弱な状態で取り組まねばならないということ）
リーマン仮説は現代数学の本流中の本流でこの問題に取り組むための道具（つまり理論）の整備を長年に亘って膨大な数学者が整備し
続けてきたが今もって全く歯が立たないという意味で本当に難しい問題
言い換えると、P≠NP問題は、それが本当にどのぐらい難しい問題なのか（しばらく前に300年余りぶりに解決されたフェルマーの大予想ほどなのか、
それよりは易しそうなのか、難しそうなのか）ということが評価できない（難しさを評価できるほど数学に組み込まれていない）という意味で難しい
少なくとも、様々な道具を揃えて多くの数学者が取り組んでいるリーマン仮説へのチャレンジに比べれば、P≠NP問題へのチャレンジは
手探りと呼んでも良いようなレベル
例えばコラッツ予想（与えられた正の整数が偶数の時は２で割り、奇数の時は３を掛けて１を足すというのを繰り返せばいつかは１になるという予想）は
実に簡単な問題に見えるが解決されないままだし、解決の見通しも今の時点では全く立っていないはず
この問題がどのぐらい難しいのかの評価も全く不明のまま
P≠NP問題は計算機科学の大問題なので非常に多くの理論計算機科学者は取り組んでいるが、現代数学の本流とは未だに繋がっておらず
その難しさが現代数学が持っている道具立てに基づいて評価できないという意味では、少し乱暴な言い方だが、コラッツ予想に似ている
フェルマーの大予想を解決したWilesさんがかつて述べていたが、フェルマーの大予想も数学の本流とは結びついていなかった（あの大予想を
解決しようとしてKummerの理想数のアイデアを整理し正当化しようという努力から代数的整数論が誕生したにもかかわらず）が、Faltingsによって
あの大予想が楕円曲線に関する谷山－志村予想と結びついたことによって現代数学（の、この投稿で言ってる意味での、本流）と結びつき位置付けられて
現代数学の問題としてどうチャレンジすべきかが見えて来た、とね
>>147
いやいや、NP完全問題の最適解がΔ_p^2だって事だよ。古くはp-selectable参照。 >159
頭わるくてすまん
「"p-selectable" np complete」でぐぐったがわからんかった
説明してくれるとありがたいのだが
>>158
同意っす
計算複雑性理論界隈の人たちの多くは、チューリングマシンや記号論理学あたりにいるっぽい。
計算モデルとして回路計算量が提案されたあたりから少し広がりは出たけど、
数学のメインストリームとは繋がりが薄い。
多くの計算量クラスを生み続けている気がする...
一方、NP完全問題とグラフ問題は親和性が高くて、
入力されるグラフを限定することで多項式時間で解けるアルゴリズムを見つけてる。
グラフ理論もまた、数学のメインストリームとは繋がりが薄い。
グラフを代数的に扱う分野はあるが、かなりマイナーである。
これらとは違う方向として、アルゴリズマーな方々は探索問題の枝刈り頑張ってて、
「(実用上は)多項式時間」というのも叩き出してたりするんだけど、
計算実験は証明じゃないしね..
ということで、現代数学の本流との架け橋を繋げられれば道は開けるのかなと。 業界的には手詰まり感が漂ってる気がする
ブレークスルーが必要なんだけど、だれも本気で分野間に橋をかけようとしてない気がする
そういう試みは業界的には無視の方向なのかもしれない
まあ、計算理論やるより、コンピュータ業界に就職する方がお金を稼げそうなので、
新しい人も入ってこないんかもね
マンハッタン計画（日本人大量虐殺実験）に携わった科学者
ユダヤ系に★をつけると
ロバート・オッペンハイマー★ ニールス・ボーア★
エンリコ・フェルミ ジョン・フォン・ノイマン★
オットー・フリッシュ★ エミリオ・セグレ★ ハンス・ベーテ★
エドワード・テラー★ ユージン・ウィグナー★ スタニスワフ・ウラム★
ハロルド・ユーリー★ ジェームズ・フランク★ リチャード・ファインマン★
etc.
ロスト・イン・トランスレーションはコッポラの娘のソフィア・コッポラ監督作品で２００３年のアカデミー賞を総なめにした
東京を舞台にした孤独な白人同士の交流を描いた作品だが、この映画は白人女が日本女をどうみていたのがよく描かれている。
マンコしかとりえがない猿のような設定だ。白人女と日本女の交流は全く描かれていない
この映画は若い頃にモデルとして来日してたキャメロン・ディアスも描かれている。キャメロン・ディアスは日本を相当嫌っていたようで
日本人の知り合いは全く出てこない。ホテルでしか酒を飲まない。
日本人のいる居酒屋は全く出てこない。白人女が日本人をどう観ていたのかよく判る傑作だぜ
ロスト・イン・トランスレーションは日本女の評判がすこぶる悪かった
あの映画は「白人女が日本女をどう見ていたのか」が強烈に描かれている
まさにイエローキャブ、マンコ猿のような設定だぜｗ日本男は主に軽薄なヤンキーとして描かれている。藤井隆だ
あの映画を観た時に日本に滞在している白人ですら日本人は猿にしか見えないと考えていると思ったね
■■■馬鹿板をスルと菅官房長官みたいな嘘吐きになります。そやし止めなさい。■■■
￥
>>158
NSは数学でも数理物理でも物理でも、重要命題かつ計算機が発達してるのに
やっぱり無理じゃないか‥‥
となってるので、とんでもなく難しいんだろうね >>59
人工知能てDLのこと？
あれの実装面で発展してるのはCNNであって、細かなミスの許される画像認識に関しては強いけど
他に関しては全然だ >>158
今は証明論の世界の人の方が成果出してんじゃん ついに証明されたぞー
https://arxiv.org/abs/1708.03486
A Solution of the P versus NP Problem
Norbert Blum
(Submitted on 11 Aug 2017)
Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove
exponential lower bounds for the monotone network complexity of the clique function and of
Andreev's function. We show that these approximators can be used to prove the same
lower bound for their non-monotone network complexity. This implies P not equal NP. >>201
> ついに証明されたぞー
凄い！
この証明が正しければ、想像してたよりも色んな意味であっけなく片が付いたというのが正直な個人的感想です
それはともかく、これが正しいならば、P≠NPという形で解決したということは多項式時間階層も潰れないから、
計算量理論屋さんにとって時間計算量クラスの間の等不等に関する未解決問題は無数に残っているので
失業の心配も当分は不要ということになる >>201
これとは全く独立だけど同じ時期にHPのパロアルト研究所の研究員のVinay Deolalikarが
１日だけプレプリントを彼のホームページに公開して「証明した」って発表して
しかも計算量の大家にしてTuring賞受賞者のStephan Cookが「まともそう」ってお墨付きを与えたものだから
大騒ぎになったけど、結局、どうも間違ってるって結論になったみたいですね
（この騒ぎのお蔭で彼の名前でオランダ語版のWikipediaにページが作られたみたいだ）
● この騒ぎに関する記事（の日本語訳…どうも翻訳の質は高くないらしい）：
http://jp.techcrunch.com/2010/08/13/20100812fuzzy-math/
● Vinay Deolalikarのプレプリント（2010年の日付になっているので温めていたのかも）のオランダのサイトにミラーされたもの（？）
https://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf
Blumがarxivにアップすることで証明を発表したので、Deolalikarは証明の先取権を主張するためにずっと温めていたのを
あわてて発表したと推察すべきかも知れない（そう推察すると、Deolalikarのプレプリントが2010年であるにもかかわらず
発表のタイミングはDeolalikarのほうが３日ほど遅い13日になったのも自然な説明がつく） >>201
査読は通ってるん?
内容について、だれか解説してくんろー >>224
> 査読は通ってるん?
査読には時間がかかる（通常の平凡な論文でも数ヶ月から長ければ半年以上も要する）ので
取り敢えずarxivに登録して公開し証明の先取権の争いが起こった際に必要となる内容・日時の証拠を確保した段階
これから学術雑誌に投稿して査読を受ける（あるいは既に投稿済で査読中という）ことになる >>236
> なんか矛盾あるみたいね
？？？
Blumのプレプリントに間違いがあるってこと？
それとも私の235の投稿の内容に何か間違いがあるの？ >>237
そうすぐには指摘できないだろうさ
さぁ語り間違いなら間違い、良い線いってるなら良い線いってる、で
熟成させてこうではないか、巻いていこう巻いていこう 唐突にお笑い芸人のモノマネとか始めて鬱陶しく絡んでくるタイプの奴やろ
この手の論文って、どこのジャーナルに投稿するもんなの?
それ以外のところに載ってるのは信憑性がないってことでおk?
>>252
ありがとうございます
なるほどRazborovさんが一蹴ですか >>252
ありがとうございます。
先を越されたかと... ^_^;;; P≠NPは我々の世代では解決できない問題であろうから、
誰かが論文を提出しても「先を越された」などと心配する必要はない
むろん、「自分なら解けるかも」などと甘ったれた期待を抱いてはいけない
>>256
解けたよん
んで、どっかに論文投稿してみる
んで、叩かれる >>267
論文投稿してみて却下されているなら、
中身が間違っており、解けてないということ。
まさか
「中身は正しいのに、査読者の意味不明なイチャモンによって掲載させてくれない」
などと勘違いしているわけではあるまいな >>268
いや、まじで「俺は信じない」って却下されてる
おいおい、査読コメントかよってなってる こういうのって、まじめに投稿しても見てくんないのかな
んで、Arxvi とかに投稿せざるをえないという。
案外、ペレルマンもそうだったのかも。
まわりから「てめーに解けるわけがない」とか言われてさ
んで、きのこ狩りなヒッキーになっちゃった
>>269
査読コメントは論文の質と合わせ鏡だよ
論文の中身があまりにもド素人まるだしのデタラメな書き方だと、
「正しいという確証が持てない」
みたいな曖昧なコメントになる
そういう論文は真偽を見極める以前の問題で、
「間違ってさえいない」(正しい、という意味ではない)
という状況になっているわけだ
>>270
P≠NPの論文だからという理由でマジメに相手してもらえないわけではなかろう。
単に、お前の論文がマジメに相手する水準に達してないってことだろう ちなみに、運が悪くて本当にヒドイ査読者に当たったという可能性も
ゼロではないので、やる気があるなら他の雑誌に投稿してみればよい
何回かトライしてみて、いつも やる気のないコメントしか返って来ないようなら、
いよいよお前の論文の中身がデタラメであると断言できる
Blumの証明、誤りってことで結論出たみたい
間違った演繹があるって
別の査読者からは「天下のP≠NP問題だぞ。舐めてんのか。ゴルァ」と。
まともそうなコメントくれたひとはいて、「(自分は判断できんので)えらい先生方が査読してるとこに出すように」と。
>>290
＞別の査読者からは「天下のP≠NP問題だぞ。舐めてんのか。ゴルァ」と。
たぶんそれは、
「天下のP≠NP問題が こんな稚拙な議論で解けるわけがないだろコノヤロー」
ということであろう
論文の中身がマジメに相手する水準に達してないってことだ。
中身がまとも(に見える)論文ならば、今回の騒動のように、
きちんと間違っている箇所を指摘してくれるものである
もう一度言うが、お前の論文はおそらく真偽を見極める以前の問題で、
「間違ってさえいない」(正しい、という意味ではない)
という状況になっているのだろう
＞まともそうなコメントくれたひとはいて、「(自分は判断できんので)えらい先生方が査読してるとこに出すように」と。
だったら別のところに出せばいいじゃん
まあ似たような反応しか返ってこないと思うけど >>270
ペレルマンのは中華大数学者様が堂々と丸パク論文出版したのに呆れ返ったからだろ
Blumのは誤りの指摘について意見聞かれたRazborovが禿同したのが決め手になった感 ペレルマンはサーストンやハミルトンの功績が無視されたのにぶち切れてたんだよ
本人がそう言ってただろう
大筋は合ってるラフな論文を行間を埋めて自分達の業績にする
ブルバキグループがさんざんやってきたこと
けどヴェイユらが居なければ、こんなに進歩しなかったよね
大企業が下請けの技術を盗んで肥え太るようなもんだから
まぁP∈NPかつP≠NPだろうな
まぁP∈NPかつPノットイコールNPだろうな
ノットイコールちゃんと表示されるかな？
流石に幾らJimちゃんねるでも数学板はちゃんと表示されるか
ついでに↓
≒
↑ニアリーイコールテスト
ブックマークへ