X
トップページ⇒数学
447コメント132KB
P vs NP
■ このスレッドは過去ログ倉庫に格納されています
0002baka描 ◆ghclfYsc82
垢版 |
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で答えるために何をしなければならないか、あるいはどんなマシンでないと
多項式時間で解けないか、ですよね？
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. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
0022馬と鹿と豚さん
垢版 |
2012/10/24(水) 23:08:56.58
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　このスレ、レス数がやや少ないので上げとくわね。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/
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
より計算量の少ないアルゴリズムが存在したらそれはええことやないか。それともあかんのか
0038１３２人目の素数さん
垢版 |
2014/03/23(日) 12:49:49.80
P vs NP問題を解決するとされている、「消滅解」って、
具体的にどういうものか知っている人いますか。
0041１３２人目の素数さん
垢版 |
2014/03/24(月) 04:34:23.24
山口人生氏の本を読んだけど、本に記されている記述が不十分なのか、私の理解力が不十分なのか分りませんが、
読んでも結局分りませんでした。
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だと、二分探索をその桁数のオーダーだけやれば解けちゃうよ
0046１３２人目の素数さん
垢版 |
2014/08/06(水) 10:19:33.62
P/NP=N^(-1)
0048１３２人目の素数さん
垢版 |
2015/03/20(金) 10:33:57.64ID:Ipb9fO2f
みきやん予想

ある位数nの群全てを多項式時間で見つけ出すアルゴリズムは存在する
0049１３２人目の素数さん
垢版 |
2015/03/22(日) 11:31:03.48ID:puQMCwvC
すみません、計算機屋のみきやんですけど反応ください
0050１３２人目の素数さん
垢版 |
2015/03/22(日) 19:44:40.59ID:puQMCwvC
改定

みきやん予想

任意の位数nの群全てを多項式時間で見つけ出すアルゴリズムは存在する
0051１３２人目の素数さん
垢版 |
2015/11/26(木) 14:50:34.17ID:2eAh2Qsb
NP≠Pを証明するのってなんでそんなに難しいの？
0053１３２人目の素数さん
垢版 |
2015/11/26(木) 22:29:26.84ID:zhCidC09
P ≠ NP を自力で証明することと
P ≠ NP 予想を誰かが解決したあとにその照明の内容を理解することはどちらが難しいか？
0054１３２人目の素数さん
垢版 |
2015/11/26(木) 23:45:39.43ID:QsskYz9S
入門書読むと、コンピュータ科学最大の難問の一つである、とか証明の努力を退けてきた、とか
いろいろ書いてあるけど、どういう試みがなされたのかとか証明につながるヒントとか
可能性がたかそうなルートとか研究の中途の説明ってないんだよねえ
誰か教えてよ
進展具合とか、もうみんな諦めちゃって手がついていないのか？
0057１３２人目の素数さん
垢版 |
2015/11/27(金) 08:59:02.08ID:d59IPEdm
まあ、俺以外の誰かだと500年くらい掛かりそうだが、俺なら200年で出来る気がするな
人生短いから、実証出来ないのが残念
0058１３２人目の素数さん
垢版 |
2015/11/27(金) 23:26:50.82ID:yXKZ7T4I
自力で証明する方が証明のチェックより難しいというのは
まさにP ≠ NP的な話だね
0059１３２人目の素数さん
垢版 |
2015/11/30(月) 20:41:22.80ID:SStpBv11
人工知能にNP問題学習させたら多項式時間で解けるようなったりして。
0063１３２人目の素数さん
垢版 |
2015/11/30(月) 23:54:07.65ID:SStpBv11
TSPの都市配置と最短経路を学習データとして
ディープラーニングで学習させたら良い解返してくれるんじゃないか。
0065１３２人目の素数さん
垢版 |
2015/12/01(火) 18:56:35.23ID:B3VaAOp4
CNFと充足解を学習データとして
ディープラーニングで学習させたらSATが多項式時間で解けるようになるかも

まあSATは無理でも素因数分解とかなら良い線いくんちゃう？
0066１３２人目の素数さん
垢版 |
2015/12/02(水) 09:03:58.81ID:uGobi9Ry
どうでもいい与太話も結構だが、君は「解ける」の意味をちゃんと理解してから書き込むように
0067１３２人目の素数さん
垢版 |
2015/12/11(金) 23:48:54.04ID:y8CRtoTw
導出原理なかなか楽しい。
鳩ノ巣原理なんかは時間かかるらしいが。
0068１３２人目の素数さん
垢版 |
2015/12/28(月) 17:02:51.40ID:f9D4SFuA
すまん、だれか教えてくれ
http://www.ti.inf.ethz.ch/ew/lehre/extremal04/raemy.pdf
これなんだが。

なぜサイズmの鳩ノ巣原理のレゾリューションの証明の中に
m^2/9個の変数を持つクローズが出てくることが言えると、
鳩ノ巣原理の証明長が指数になることが言えるの？
m^2/9個の変数を持つクローズが全部出てくるの？
0069１３２人目の素数さん
垢版 |
2016/02/15(月) 03:36:11.05ID:8JYeZ3jx
記述計算量において、
Pは「最小不動点演算子を持つ一階述語論理」で、
NPは「存在量化二階述語論理」であらわされる。
「最小不動点演算子を持つ一階述語論理」の無矛盾性を
「存在量化二階述語論理」で証明できれば、
ゲーデルの第二不完全性定理より、
「最小不動点演算子を持つ一階述語論理」より
「存在量化二階述語論理」が大きいと言えるから、
P≠NPも言えるのではないか。
この証明、どうだろう？
0071１３２人目の素数さん
垢版 |
2016/02/21(日) 01:13:18.21ID:l/2Y/c0/
述語論理の公理系の規則が全てトートロジーである事から証明できると思います。
0072１３２人目の素数さん
垢版 |
2016/05/13(金) 20:27:09.69ID:BegVM+5s
たとえばP vs NP が連続体仮説の結果に依存するとかいう可能性はあるの？
0073１３２人目の素数さん
垢版 |
2016/05/13(金) 21:59:07.26ID:BegVM+5s
あるいはビジービーバーみたいにＮＰを多項式で解くアルゴリズムは存在することはするけど、
どのアルゴリズムがそれかは絶対わからないとか。
0075１３２人目の素数さん
垢版 |
2016/10/08(土) 01:36:08.57ID:uDpf+4BC
俺が証明したらフィールズ賞くれるの？
0097１３２人目の素数さん
垢版 |
2017/05/14(日) 11:51:51.33ID:6zDFiTmB
いきなりすまん。
解けたけど、(自分以外)だれも理解できないっぼい。
ペレルマンさんの気持ちがわかる気がする。
0098１３２人目の素数さん
垢版 |
2017/05/14(日) 11:56:23.33ID:6zDFiTmB
フィールズ賞もらえる歳は超えちまった。
ちなみに、フィールズ賞(ノーベル賞もだけど)は税金がかからんが、
クレイ研究所が提示してる方は免除の記載が無いらしいので、
このままだと半分が税金。
0109１３２人目の素数さん
垢版 |
2017/05/14(日) 12:32:18.46ID:lg6ZUYhf
>>97-98
人生２世さん乙〜ｗ　（人生さんはあの第２巻は出さず終いなんだろうなあｗ）

P vs NP問題を解決した場合、もらえるのはフィールズ賞（純粋数学）じゃなくてネヴァンリンナ賞（理論計算機科学）だ
ちなみに年齢制限に関しては超えていても本当に解決したのならば特別賞が与えらえるだろうね
フェルマー大予想を解決したワイルズさんも（受賞時でなく）解決時に既に40歳の制限を超えていたがICM 1998でフィールズ賞の特別賞を受賞した
年齢制限はフィールズ賞を授与するICMの前年中に40歳に達していたらＮＧとのこと
011097
垢版 |
2017/05/14(日) 12:47:57.84ID:6zDFiTmB
>>109
れすありがと。人生さんいたね。懐かしー
んで、ネヴァンリンナ賞なんですね。情報ありがとう。
ちなみに年齢制限は余裕で超えてるw
011197
垢版 |
2017/05/14(日) 12:54:23.47ID:6zDFiTmB
他の最近の研究動向調べてて思ったんだけど、この問題って、人気なさ気だなと。
しかも、一般的にも認知度が低い。リーマン問題さんがうらやましいww
0122１３２人目の素数さん
垢版 |
2017/05/15(月) 03:23:33.41ID:9zy0+xIM
>>111
知名度は低いかも知れませんけど
応用範囲の広さは随一でしょう
もっともP≠NPの可能性が高いですから
能率的なアルゴリズムが生まれるのではないですが
暗号の安全性という意味ではP≠NPが望ましい結果です
0133１３２人目の素数さん
垢版 |
2017/05/20(土) 12:21:03.73ID:QqOpEWlW
NP完全問題をPで解けるアルゴリズムがある(だがその方法で最適解が求まる訳では無い)、とか、Pではあるんだが、O(n^10000) とかだったらどう？
0134１３２人目の素数さん
垢版 |
2017/05/20(土) 12:32:23.80ID:x8e1GjEa
>>133
前者は解けるとは言わない。近似解アルゴリズムならいくらでも手抜きできる
後者はそのままだと困難だけど改良の余地がある
0135１３２人目の素数さん
垢版 |
2017/05/20(土) 17:34:56.02ID:dtYVrowk
>>133 例えば背理法を用いて、P \neq NP を仮定して矛盾を示したとする。
(背理法で解けるという主張では無く、あくまで例です)

この時、存在は示されてたものの、
具体的に解を求めるアルゴリズムは示されて無いので、
実用性の面では役に立たない。

存在証明だけで凄い事ではあるんだろうけど。
0146１３２人目の素数さん
垢版 |
2017/05/31(水) 19:52:34.74ID:0qbtak2u
>>133
SATだったら変数に真か偽か入れてはプログラムを動かせば、変数の数の回数だけ動かして、一つの解が求まる。
クソ遅い方はどうなんだろう。
素数判定は6乗位だったと思うけど実装されて、使われているのかな？
0147１３２人目の素数さん
垢版 |
2017/06/01(木) 01:30:33.14ID:nBxIGcKX
>>146
示されている方法でSATを解くと、
組み合わせ分を試すわけなので指数オーダーになるよ。
AKS素数判定法での計算量は (Wikiによると) \tild{O}(log(n)^7.5) っぽい。
でも、実際には使われてないだろうなー
0158１３２人目の素数さん
垢版 |
2017/06/02(金) 17:42:11.15ID:bfJzN9YC
P≠NP問題は大多数の数学者が研究している現代数学の本流（代数、解析、幾何）からは遠く離れた辺境（計算機科学）で生まれた問題で
現在でも、研究が進んで道具立てが整備されている数学の本流とは結びついていないので難しい（難問に立ち向かうための道具が
貧弱な状態で取り組まねばならないということ）

リーマン仮説は現代数学の本流中の本流でこの問題に取り組むための道具（つまり理論）の整備を長年に亘って膨大な数学者が整備し
続けてきたが今もって全く歯が立たないという意味で本当に難しい問題

言い換えると、P≠NP問題は、それが本当にどのぐらい難しい問題なのか（しばらく前に300年余りぶりに解決されたフェルマーの大予想ほどなのか、
それよりは易しそうなのか、難しそうなのか）ということが評価できない（難しさを評価できるほど数学に組み込まれていない）という意味で難しい
少なくとも、様々な道具を揃えて多くの数学者が取り組んでいるリーマン仮説へのチャレンジに比べれば、P≠NP問題へのチャレンジは
手探りと呼んでも良いようなレベル

例えばコラッツ予想（与えられた正の整数が偶数の時は２で割り、奇数の時は３を掛けて１を足すというのを繰り返せばいつかは１になるという予想）は
実に簡単な問題に見えるが解決されないままだし、解決の見通しも今の時点では全く立っていないはず
この問題がどのぐらい難しいのかの評価も全く不明のまま

P≠NP問題は計算機科学の大問題なので非常に多くの理論計算機科学者は取り組んでいるが、現代数学の本流とは未だに繋がっておらず
その難しさが現代数学が持っている道具立てに基づいて評価できないという意味では、少し乱暴な言い方だが、コラッツ予想に似ている

フェルマーの大予想を解決したWilesさんがかつて述べていたが、フェルマーの大予想も数学の本流とは結びついていなかった（あの大予想を
解決しようとしてKummerの理想数のアイデアを整理し正当化しようという努力から代数的整数論が誕生したにもかかわらず）が、Faltingsによって
あの大予想が楕円曲線に関する谷山−志村予想と結びついたことによって現代数学（の、この投稿で言ってる意味での、本流）と結びつき位置付けられて
現代数学の問題としてどうチャレンジすべきかが見えて来た、とね
0160１３２人目の素数さん
垢版 |
2017/06/03(土) 08:55:44.87ID:FbuAHE0y
>159
頭わるくてすまん
「"p-selectable" np complete」でぐぐったがわからんかった
説明してくれるとありがたいのだが
0161１３２人目の素数さん
垢版 |
2017/06/03(土) 09:29:55.55ID:FbuAHE0y
>>158
同意っす

計算複雑性理論界隈の人たちの多くは、チューリングマシンや記号論理学あたりにいるっぽい。
計算モデルとして回路計算量が提案されたあたりから少し広がりは出たけど、
数学のメインストリームとは繋がりが薄い。
多くの計算量クラスを生み続けている気がする...

一方、NP完全問題とグラフ問題は親和性が高くて、
入力されるグラフを限定することで多項式時間で解けるアルゴリズムを見つけてる。
グラフ理論もまた、数学のメインストリームとは繋がりが薄い。
グラフを代数的に扱う分野はあるが、かなりマイナーである。

これらとは違う方向として、アルゴリズマーな方々は探索問題の枝刈り頑張ってて、
「(実用上は)多項式時間」というのも叩き出してたりするんだけど、
計算実験は証明じゃないしね..

ということで、現代数学の本流との架け橋を繋げられれば道は開けるのかなと。
0162161
垢版 |
2017/06/03(土) 09:39:53.50ID:FbuAHE0y
業界的には手詰まり感が漂ってる気がする
ブレークスルーが必要なんだけど、だれも本気で分野間に橋をかけようとしてない気がする
そういう試みは業界的には無視の方向なのかもしれない

まあ、計算理論やるより、コンピュータ業界に就職する方がお金を稼げそうなので、
新しい人も入ってこないんかもね
0173１３２人目の素数さん
垢版 |
2017/06/12(月) 16:24:00.33ID:3ur0Moka
マンハッタン計画（日本人大量虐殺実験）に携わった科学者
ユダヤ系に★をつけると

ロバート・オッペンハイマー★ ニールス・ボーア★
エンリコ・フェルミ 　　ジョン・フォン・ノイマン★
オットー・フリッシュ★ エミリオ・セグレ★ ハンス・ベーテ★
エドワード・テラー★ ユージン・ウィグナー★ スタニスワフ・ウラム★
ハロルド・ユーリー★ ジェームズ・フランク★ リチャード・ファインマン★
etc.
0174１３２人目の素数さん
垢版 |
2017/06/12(月) 16:31:36.40ID:3ur0Moka
ロスト・イン・トランスレーションはコッポラの娘のソフィア・コッポラ監督作品で２００３年のアカデミー賞を総なめにした
東京を舞台にした孤独な白人同士の交流を描いた作品だが、この映画は白人女が日本女をどうみていたのがよく描かれている。
マンコしかとりえがない猿のような設定だ。白人女と日本女の交流は全く描かれていない
この映画は若い頃にモデルとして来日してたキャメロン・ディアスも描かれている。キャメロン・ディアスは日本を相当嫌っていたようで
日本人の知り合いは全く出てこない。ホテルでしか酒を飲まない。
日本人のいる居酒屋は全く出てこない。白人女が日本人をどう観ていたのかよく判る傑作だぜ
0175１３２人目の素数さん
垢版 |
2017/06/12(月) 16:32:57.83ID:3ur0Moka
ロスト・イン・トランスレーションは日本女の評判がすこぶる悪かった
あの映画は「白人女が日本女をどう見ていたのか」が強烈に描かれている
まさにイエローキャブ、マンコ猿のような設定だぜｗ日本男は主に軽薄なヤンキーとして描かれている。藤井隆だ
あの映画を観た時に日本に滞在している白人ですら日本人は猿にしか見えないと考えていると思ったね
0176￥ ◆2VB8wsVUoo
垢版 |
2017/06/12(月) 16:54:15.42ID:Lt75QqGT
■■■馬鹿板をスルと菅官房長官みたいな嘘吐きになります。そやし止めなさい。■■■

￥
0187１３２人目の素数さん
垢版 |
2017/06/12(月) 23:27:31.96ID:wX/ODItS
>>158
NSは数学でも数理物理でも物理でも、重要命題かつ計算機が発達してるのに
やっぱり無理じゃないか‥‥
となってるので、とんでもなく難しいんだろうね
0188１３２人目の素数さん
垢版 |
2017/06/13(火) 15:01:47.38ID:/URkUpsU
>>59
人工知能てDLのこと？
あれの実装面で発展してるのはCNNであって、細かなミスの許される画像認識に関しては強いけど
他に関しては全然だ
0201１３２人目の素数さん
垢版 |
2017/08/15(火) 19:23:24.35ID:thmGAPfN
ついに証明されたぞー
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.
0212１３２人目の素数さん
垢版 |
2017/08/16(水) 01:06:31.87ID:jEeCkROO
>>201
> ついに証明されたぞー

凄い！
この証明が正しければ、想像してたよりも色んな意味であっけなく片が付いたというのが正直な個人的感想です
それはともかく、これが正しいならば、P≠NPという形で解決したということは多項式時間階層も潰れないから、
計算量理論屋さんにとって時間計算量クラスの間の等不等に関する未解決問題は無数に残っているので
失業の心配も当分は不要ということになる
0223１３２人目の素数さん
垢版 |
2017/08/17(木) 17:59:53.52ID:jtkTJYdp
>>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日になったのも自然な説明がつく）
0224１３２人目の素数さん
垢版 |
2017/08/17(木) 23:29:31.57ID:eEGidgoV
>>201
査読は通ってるん?
内容について、だれか解説してくんろー
0235１３２人目の素数さん
垢版 |
2017/08/18(金) 14:46:00.86ID:VqSR3OPH
>>224
> 査読は通ってるん?

査読には時間がかかる（通常の平凡な論文でも数ヶ月から長ければ半年以上も要する）ので
取り敢えずarxivに登録して公開し証明の先取権の争いが起こった際に必要となる内容・日時の証拠を確保した段階
これから学術雑誌に投稿して査読を受ける（あるいは既に投稿済で査読中という）ことになる
0237１３２人目の素数さん
垢版 |
2017/08/18(金) 19:38:01.81ID:VqSR3OPH
>>236
> なんか矛盾あるみたいね

？？？
Blumのプレプリントに間違いがあるってこと？
それとも私の235の投稿の内容に何か間違いがあるの？
0238１３２人目の素数さん
垢版 |
2017/08/18(金) 20:09:01.47ID:lK+QT0Lh
>>237
そうすぐには指摘できないだろうさ

さぁ語り間違いなら間違い、良い線いってるなら良い線いってる、で
熟成させてこうではないか、巻いていこう巻いていこう
0240１３２人目の素数さん
垢版 |
2017/08/18(金) 21:01:45.28ID:61PvyiN2
唐突にお笑い芸人のモノマネとか始めて鬱陶しく絡んでくるタイプの奴やろ
0241224
垢版 |
2017/08/18(金) 21:17:02.84ID:um7BHonj
この手の論文って、どこのジャーナルに投稿するもんなの?
それ以外のところに載ってるのは信憑性がないってことでおk?
0253237
垢版 |
2017/08/18(金) 21:58:35.34ID:VqSR3OPH
>>252
ありがとうございます
なるほどRazborovさんが一蹴ですか
0255１３２人目の素数さん
垢版 |
2017/08/19(土) 01:01:27.48ID:BXKrqwr2
>>252
ありがとうございます。
先を越されたかと... ^_^;;;
0256１３２人目の素数さん
垢版 |
2017/08/19(土) 01:44:26.01ID:2IbjO0BA
P≠NPは我々の世代では解決できない問題であろうから、
誰かが論文を提出しても「先を越された」などと心配する必要はない

むろん、「自分なら解けるかも」などと甘ったれた期待を抱いてはいけない
0267１３２人目の素数さん
垢版 |
2017/08/19(土) 05:09:22.72ID:BXKrqwr2
>>256
解けたよん
んで、どっかに論文投稿してみる
んで、叩かれる
0268１３２人目の素数さん
垢版 |
2017/08/19(土) 05:20:59.80ID:2IbjO0BA
>>267
論文投稿してみて却下されているなら、
中身が間違っており、解けてないということ。
まさか

「中身は正しいのに、査読者の意味不明なイチャモンによって掲載させてくれない」

などと勘違いしているわけではあるまいな
0269１３２人目の素数さん
垢版 |
2017/08/19(土) 05:52:09.62ID:BXKrqwr2
>>268
いや、まじで「俺は信じない」って却下されてる
おいおい、査読コメントかよってなってる
0270１３２人目の素数さん
垢版 |
2017/08/19(土) 05:55:14.63ID:BXKrqwr2
こういうのって、まじめに投稿しても見てくんないのかな
んで、Arxvi とかに投稿せざるをえないという。
案外、ペレルマンもそうだったのかも。
まわりから「てめーに解けるわけがない」とか言われてさ
んで、きのこ狩りなヒッキーになっちゃった
0286１３２人目の素数さん
垢版 |
2017/08/19(土) 06:44:12.60ID:2IbjO0BA
>>269
査読コメントは論文の質と合わせ鏡だよ
論文の中身があまりにもド素人まるだしのデタラメな書き方だと、

「正しいという確証が持てない」

みたいな曖昧なコメントになる
そういう論文は真偽を見極める以前の問題で、

「間違ってさえいない」(正しい、という意味ではない)

という状況になっているわけだ

>>270
P≠NPの論文だからという理由でマジメに相手してもらえないわけではなかろう。
単に、お前の論文がマジメに相手する水準に達してないってことだろう
0287１３２人目の素数さん
垢版 |
2017/08/19(土) 06:53:01.05ID:2IbjO0BA
ちなみに、運が悪くて本当にヒドイ査読者に当たったという可能性も
ゼロではないので、やる気があるなら他の雑誌に投稿してみればよい

何回かトライしてみて、いつも やる気のないコメントしか返って来ないようなら、
いよいよお前の論文の中身がデタラメであると断言できる
0289１３２人目の素数さん
垢版 |
2017/08/19(土) 07:26:24.65ID:rLIdD+gJ
Blumの証明、誤りってことで結論出たみたい
間違った演繹があるって
0290１３２人目の素数さん
垢版 |
2017/08/19(土) 08:27:09.03ID:VEYeO0OZ
別の査読者からは「天下のP≠NP問題だぞ。舐めてんのか。ゴルァ」と。
まともそうなコメントくれたひとはいて、「(自分は判断できんので)えらい先生方が査読してるとこに出すように」と。
0301１３２人目の素数さん
垢版 |
2017/08/19(土) 17:45:38.48ID:2IbjO0BA
>>290
＞別の査読者からは「天下のP≠NP問題だぞ。舐めてんのか。ゴルァ」と。

たぶんそれは、

「天下のP≠NP問題が こんな稚拙な議論で解けるわけがないだろコノヤロー」

ということであろう
論文の中身がマジメに相手する水準に達してないってことだ。

中身がまとも(に見える)論文ならば、今回の騒動のように、
きちんと間違っている箇所を指摘してくれるものである
もう一度言うが、お前の論文はおそらく真偽を見極める以前の問題で、

「間違ってさえいない」(正しい、という意味ではない)

という状況になっているのだろう


＞まともそうなコメントくれたひとはいて、「(自分は判断できんので)えらい先生方が査読してるとこに出すように」と。

だったら別のところに出せばいいじゃん
まあ似たような反応しか返ってこないと思うけど
0314sage
垢版 |
2017/08/24(木) 00:45:01.27ID:3y090A1B
平面グラフに対する三色問題を高速で解けるとの主張だが、よくわからん。
ttps://www.quora.com/If-I-proved-that-P-NP-would-you-want-to-know-what-that-proof-is
0325１３２人目の素数さん
垢版 |
2017/08/25(金) 15:04:15.27ID:Qo0CVRfU
>>270
ペレルマンのは中華大数学者様が堂々と丸パク論文出版したのに呆れ返ったからだろ

Blumのは誤りの指摘について意見聞かれたRazborovが禿同したのが決め手になった感
0326１３２人目の素数さん
垢版 |
2017/08/25(金) 19:04:23.64ID:mSVjoa1H
ペレルマンはサーストンやハミルトンの功績が無視されたのにぶち切れてたんだよ
本人がそう言ってただろう
0327１３２人目の素数さん
垢版 |
2017/08/25(金) 19:26:09.59ID:NCATUS94
大筋は合ってるラフな論文を行間を埋めて自分達の業績にする

ブルバキグループがさんざんやってきたこと
0341１３２人目の素数さん
垢版 |
2018/05/01(火) 19:29:03.87ID:21rJWgQ2
耳栓をしたら世界が変わってワロタ
0352１３２人目の素数さん
垢版 |
2018/05/20(日) 21:52:16.79ID:N/saMlPT
耳栓をしたら世界が変わってワロタ
0353１３２人目の素数さん
垢版 |
2018/07/11(水) 06:46:55.70ID:UnQmpjGV
これついに証明されたらしいぞ
ニュースになってた
0356１３２人目の素数さん
垢版 |
2018/07/11(水) 14:43:32.85ID:HJQFUmmh
まぁP∈NPかつP≠NPだろうな
まぁP∈NPかつPノットイコールNPだろうな

ノットイコールちゃんと表示されるかな？
0357１３２人目の素数さん
垢版 |
2018/07/11(水) 14:45:01.28ID:HJQFUmmh
流石に幾らJimちゃんねるでも数学板はちゃんと表示されるか
ついでに↓
≒
↑ニアリーイコールテスト
0360１３２人目の素数さん
垢版 |
2020/10/02(金) 16:36:19.23ID:k94hyzCE
真田重雄は地獄へ落ちて幾十年だな
0362◆Ph05QxAcng
垢版 |
2022/05/10(火) 01:09:16.81ID:weJoFrgJ
https://www.nikkei-science.com/201212_060.html

ジグソーパズルの問題、としては解の判定は一瞬でわかるけれども、解に辿り着くまでは、多項式時間、多項式で計算量終わらない気がしますね。

最良のアルゴリズムの定義とかも考えないといけなさそうです。

まずアルゴリズムにおいて最良とは何か？
題意にたいしてどのような値が与えられても必ず解答に辿り着くアルゴリズムの中で最も計算量が少ないもの、と想像がつく。


解けるかは知りませんが続くと思います。
0363◆Ph05QxAcng
垢版 |
2022/05/10(火) 01:10:31.47ID:weJoFrgJ
ジグソーパズルの問題の最良のアルゴリズムは多項式の計算量で表現されるんですかね？
0364◆Ph05QxAcng
垢版 |
2022/05/10(火) 01:17:34.21ID:weJoFrgJ
問題の解を得られるアルゴリズムの集合をAlgと置く。


その中で最小=最良のものは存在する。
0365◆Ph05QxAcng
垢版 |
2022/05/10(火) 01:19:56.01ID:weJoFrgJ
最小(最良)のものをAns
と置く。

P =NPを否定したいなら
検証が一瞬で終わるものの中にAnsが多項式で終わらないものがある事を示す

でいいのだろうか？




まだ自分の理解が不十分な可能性があるが。
0366◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:04:11.40ID:weJoFrgJ
Algの中で最大のものは全探索のアルゴリズムである
これをWorstと置く。
0367◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:23:37.29ID:weJoFrgJ
>>365
検証が一瞬というのはあまり正確な表現ではなく
検証が多項式時間で終わるものの中にAnsが多項式時間より大きな数で表現されるものの存在を示す


と言うのが正確な表現ですかね。
0368◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:29:11.38ID:weJoFrgJ
>>365
最良のアルゴリズムが一つとは限らない。
しかし、計算量は最小である。

この場合どのような手法を取るべきか。
計算量に着目すべきかどうか。
0369◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:32:04.17ID:weJoFrgJ
>>368
多分最小の計算量に着目すべきかも
0370◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:41:46.69ID:weJoFrgJ
問題はWorst が多項式ではないNPの時に、Ansが多項式になるかだ。

abs(Ans)が多項式になるかだ。ここでabs(A)はアルゴリズムAの計算量と定義する。
0371◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:53:17.98ID:weJoFrgJ
解かなくてはならない問題の定義と性質を調べなければならない気がしてきた



問題から生じる最大次数の多項式の集合をKとする


これもおかしいな。
最大計算量が指数計算量だったらこれは成り立たないから、何か性質を付加するなりして、そこら辺の判別も行わないと。
0372◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:53:31.28ID:weJoFrgJ
気になって気になって眠れなくなってきた
0373◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:59:09.52ID:weJoFrgJ
問題の定義は何だ？
0374◆Ph05QxAcng
垢版 |
2022/05/10(火) 03:59:48.69ID:weJoFrgJ
計算量は問題に依存するから問題の定義も何とかしないといけないのかもしれない。
0375◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:05:55.81ID:weJoFrgJ
ジグソーパズルの問題は全探索なら指数時間

ここで何故指数時間になるか考えないと。
指数時間になる問題と多項式時間になる問題の判別は何処だ？
0376◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:07:40.16ID:weJoFrgJ
年齢を当てる問題なら、年齢の上限があるなら、全探索は多項式時間だが、二分探索なら次数が落ちて対数になる。
0377◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:14:36.08ID:weJoFrgJ
要するに全探索で多項式計算量にならないものの中でAnsが多項式計算量にならないものの存在を示せばいい、と言うのがP!=NPか


P!=NPで確定したとは言ってないが
つまりP=NPの可能性も探りつつやります
0378◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:18:23.44ID:weJoFrgJ
命題が定める計算領域の絶対値=abs (Worst)が多項式で収まらないものの中にabs(Ans)が多項式で収まらないものの存在を示す、か、具体的に作るか
0379◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:20:40.02ID:weJoFrgJ
>>378
ここで、計算領域は常に上に有界である
0380◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:22:48.10ID:weJoFrgJ
上に有界な多項式計算量で収まらない計算領域が与えられて、その中にある最良の計算手法、アルゴリズムが存在し(確定)、しかしその計算量は多項式計算量に収まらない命題が存在する、か否か。
0381◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:25:50.52ID:weJoFrgJ
>>380
ここで言う解の定義は何だ？
命題が定める性質を持つ、ある数の組の事か？

ここでの直観、イメージは指数時間の膨大な、巨大な計算領域の中に多項式時間で収まるアルゴリズムなんて本当にあるのだろうか？
0382◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:26:21.07ID:weJoFrgJ
仕事に支障が出るのでもうやめておこう
0383◆Ph05QxAcng
垢版 |
2022/05/10(火) 04:34:11.28ID:weJoFrgJ
全てのNPのAnsはPだったとして矛盾を導く
0384◆Ph05QxAcng
垢版 |
2022/05/11(水) 00:41:43.92ID:5+iuQDKw
問題は、P!=NPを示したい場合、NP問題で最良のアルゴリズムが多項式計算量にならない事を示したい。


横一列の
a[1],,,,a[N]を与えて(これは1からNまで昇順に並んでいる)
a[1]=1だけ与えられて、
次にb[2],,,b[N]が与えられてそれぞれには2以上N以下の数字が入ってるが何が入ってるかは不明。他の情報は全てブラックボックス。a[1]の右隣当てられたら次はそのさらに右隣を当てて行ってb[N]の数列を確定させる、ジグソーパズルの一次元版を考える。置こうとしてるマス目の値が前のマスの値+1になってたらTrueを返して、違ったらFalseを返すゲーム。
これだとプレイヤーはどう足掻いても(N-1)!の計算量から逃れられないのではないだろうか。最良のアルゴリズムの計算量も(N-1)!で、P!=NPになるのではないか？


間違っているかもしれませんが、今日はここまで考えました。
0385◆Ph05QxAcng
垢版 |
2022/05/11(水) 00:53:06.39ID:5+iuQDKw
あー、ちょっと間違えたかな。

多項式時間とN!ってどっちが計算量多いんですかね。
0386◆Ph05QxAcng
垢版 |
2022/05/11(水) 00:55:12.38ID:5+iuQDKw
んー、でも一応NPだからいいのか？
0387◆Ph05QxAcng
垢版 |
2022/05/11(水) 00:59:28.13ID:5+iuQDKw
N!は2^Nより大きいからNPか
0388◆Ph05QxAcng
垢版 |
2022/05/11(水) 10:54:24.79ID:G0b+lZKs
>>384
これでP!=NP(P≠NP)の解答になっていませんかね？

何か勘違いしていたらすみません。
0389◆Ph05QxAcng
垢版 |
2022/05/11(水) 23:27:30.89ID:YiWiwdjF
>>384
これでP vs NP終わってませんかね？
このゲームの問題を解くアルゴリズムが最良でも(N-1)!の計算量が必要であり、一方解の検証は即座に終わるのは明らか。よってこの問題はNPであるがPではない。よってP≠NPである。


https://kotobank.jp/word/P対NP問題-156094


反応が欲しいんですけれども。
0390◆Ph05QxAcng
垢版 |
2022/05/11(水) 23:28:00.99ID:YiWiwdjF
もちろん間違っている可能性もありますが。
0391◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:04:21.17ID:VbVOHa6M
本当に気になって気になって仕方がないのですが、何か間違いがあったら指摘して頂きたいです。
0392◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:23:36.02ID:VNiGsFzW
あー、ミスったかも
0393◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:24:38.75ID:VNiGsFzW
二分探索が使えるのかな
0394◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:24:47.33ID:VNiGsFzW
間違えたかもしれません
0395◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:28:08.87ID:VNiGsFzW
あー、ダメっぽいな

撤回かな
0396◆Ph05QxAcng
垢版 |
2022/05/12(木) 00:30:52.72ID:VNiGsFzW
もう一度考えてみます
0397◆Ph05QxAcng
垢版 |
2022/05/13(金) 02:49:01.57ID:LPjiuv4P
俺が考えたP vs NPの問題では
全探索では(N-1)!だが
二分探索ではlog ((N-1)!)の計算量になるが、
この問題ではどう足掻いても、どんなにアルゴリズムを改良して、最高、最良のアルゴリズムを作っても多項式計算量にはならないと思う。


log (N!)と多項式計算量N^aはどっちが大きいんだ？→直観でわからないならNを莫大な数にしてさっさと計算させれば良い、というか単純にlog(N!)とNを比べれば良い。明らかに前者。

俺の作った問題で多項式計算量のアルゴリズムが存在しない事を示せば良いか。今作った問題で多項式計算量のアルゴリズムAnsが存在したとする。次にAnsの次数かつ定数aが存在する。a<=N-1である。そして明らかにa=f(N)となる関数fが存在する。fは問題によって定まる。というか、定数ならどんなNが来ても定数なのだから、N=1だった場合0か1が返ってくるから候補として0が与えられるが、そんなわけないので矛盾するから多項式計算量のアルゴリズムは存在しない？


多項式計算量のアルゴリズムってどんな集合だ？

forで回す箇所が有限個の問題だ。
全探索の試行回数がNが増加するにつれてどれくらい大きくなるのか、によって最良のアルゴリズムがどの程度のものか、　測るというのはどうだろうか？

多項式で終わるなら次数もNの関数になる？そこはどうなんだ？いや違う。定数だ。次数にNが入ったら指数計算量になる。
0398◆Ph05QxAcng
垢版 |
2022/05/13(金) 23:05:34.68ID:HYyFKuFH
二分探索が使えない設定の問題を作るか、そもそもこの問題で最良のアルゴリズムが多項式で表現出来ない事を示すか、だ。

b[N]の並びが最悪の場合で多項式計算量で求まったとして、
要素を追加したb[N+1]を追加したら、計算量の増加はa-1次の多項式で表現出来るのか？増加量も多項式にならないといけない。N=2^nとする。


そもそも多項式計算量で済む問題って選択、試行回数がNに依存しない問題だけではないだろうか。

本当に1からNまでのランダムの並びであるb[N]の並びをYes/Noでしか判定出来ない問題を、全て特定する為に多項式計算量で押さえられるだろうか？普通に考えて、常識的な感覚ならどう見ても無理。ここの矛盾を示したい。というか、これは要するに暗号を解くのは指数時間以上いる事を示すのと同値か。暗号を多項式時間では解けない事を示す。

というか、1文字特定するとか、回数に制限があれば、多項式で抑えられる。しかし試行回数がNの関数だと多項式で抑えられないと思う。そこをどう表現するか、なのだろうか。二分探索の5以上か否かの判定を組み込めない問題は作っていいのか？完全に一致した時以外を返さない問題は作れないだろうか。

まず、試行回数がNの関数になってるのと有限回なので本質的に問題の構造が異なる？問題なのか計算量なのか。




最良のアルゴリズムの計算量の式を
p(N)と置く。ここでpは多項式である。
Nが∞に近づくとp(N+1)/p(N)が1より大きな数に収束する事を示す？あるいは1に収束したと仮定して矛盾を導く？

もし、1に収束したら、問題を解く難易度がほとんど変わらない、という意味だと思う。が、そんなわけある筈ない。ここで難易度の定義や多寡が計算量に依存していると示唆される。N=1,2で全然量が違う。

WorstはN!である。

或いは二分探索よりよいアルゴリズムがないか、とか。問題を二分探索より早く解くアルゴリズムが存在しない、すなわち計算量はlog (N-1)!が最良である事を示すか。
0399◆Ph05QxAcng
垢版 |
2022/05/13(金) 23:05:49.04ID:HYyFKuFH
二分探索が使えない設定の問題を作るか、そもそもこの問題で最良のアルゴリズムが多項式で表現出来ない事を示すか、だ。

b[N]の並びが最悪の場合で多項式計算量で求まったとして、
要素を追加したb[N+1]を追加したら、計算量の増加はa-1次の多項式で表現出来るのか？増加量も多項式にならないといけない。N=2^nとする。


そもそも多項式計算量で済む問題って選択、試行回数がNに依存しない問題だけではないだろうか。

本当に1からNまでのランダムの並びであるb[N]の並びをYes/Noでしか判定出来ない問題を、全て特定する為に多項式計算量で押さえられるだろうか？普通に考えて、常識的な感覚ならどう見ても無理。ここの矛盾を示したい。というか、これは要するに暗号を解くのは指数時間以上いる事を示すのと同値か。暗号を多項式時間では解けない事を示す。

というか、1文字特定するとか、回数に制限があれば、多項式で抑えられる。しかし試行回数がNの関数だと多項式で抑えられないと思う。そこをどう表現するか、なのだろうか。二分探索の5以上か否かの判定を組み込めない問題は作っていいのか？完全に一致した時以外を返さない問題は作れないだろうか。

まず、試行回数がNの関数になってるのと有限回なので本質的に問題の構造が異なる？問題なのか計算量なのか。




最良のアルゴリズムの計算量の式を
p(N)と置く。ここでpは多項式である。
Nが∞に近づくとp(N+1)/p(N)が1より大きな数に収束する事を示す？あるいは1に収束したと仮定して矛盾を導く？

もし、1に収束したら、問題を解く難易度がほとんど変わらない、という意味だと思う。が、そんなわけある筈ない。ここで難易度の定義や多寡が計算量に依存していると示唆される。N=1,2で全然量が違う。

WorstはN!である。

或いは二分探索よりよいアルゴリズムがないか、とか。問題を二分探索より早く解くアルゴリズムが存在しない、すなわち計算量はlog (N-1)!が最良である事を示すか。
0400◆Ph05QxAcng
垢版 |
2022/05/13(金) 23:06:01.62ID:HYyFKuFH
一発でb[1]を特定する事は不可能。
この問題はb[1]を最も早く特定する問題に帰着出来るか？それとも一気に複数特定出来る方法があるのか？


b[1]からb[N]までランダムに並べてそれらを特定する、というゲームなら計算量はN!

この問題はb[i]が文字なのか数字なのかでも計算量変わる気がする、と思ったが一行増えるぐらいか？二分探索するなら全て数値化しないといけない。

一文字特定するのに二分探索が最良である事を示す→次に複数の文字列を一気に特定するのは1文字ずつ特定するより計算量が多い事を示す→問題は解ける？


とりあえず一文字特定するには二分探索が最良である事を示したい。→よく考えたらlog Nで多項式より小さい。が、最善のアルゴリズムかは不明。
例えばN=128で二分探索未満の特定する方法は存在するのか？無理だと思うが。
二分探索は計算領域を狭めて行く収束速度を考察すると良いかも知れない。

結局探索においてパソコンは命題の真か偽の判定をするだけである。命題のブール値を返すだけである。
0401１３２人目の素数さん
垢版 |
2022/05/14(土) 00:40:08.69ID:njzFtL4x
log(N!)はo(N^2)だから多項式計算量だけど
多項式ってのは2次式でも3次式でも1000次式でもいい
0402◆Ph05QxAcng
垢版 |
2022/05/14(土) 04:48:22.39ID:U+rv/M0t
>>401
どうやるんですかね、後で考えてみますね
0403◆Ph05QxAcng
垢版 |
2022/05/14(土) 04:49:08.29ID:U+rv/M0t
これから書く事は間違ってる可能性も十分ありますが、




b[N]が多項式計算量で収まったとすると、最高次数aが存在し、またその最高次数aと同じ計算量の、有限個のk個を特定する問題b[k]を求めよ、という問題が生まれる。ところがどう見てもb[N]を特定する問題はそれより計算量が多いので矛盾する。よってb[N]を求めるアルゴリズムは多項式計算量で収まらないので検証は一瞬だがNP問題に含まれる問題の存在が示されたのでP≠NPが示された？のでいいのか？
0404１３２人目の素数さん
垢版 |
2022/05/14(土) 10:19:28.01ID:Nhxe/Fh2
> b[N]を特定する問題

この問題がNP完全でないとダメ

https://ja.wikipedia.org/wiki/NP%E5%9B%B0%E9%9B%A3
> P≠NP予想との関係
> もし、いずれかのNP困難な問題を多項式時間で解くアルゴリズムが存在したなら、
> NPの全ての問題について多項式時間で解けることになり、P=NPが成り立つ。
> ところが、P=NPが成立しても「任意のNP困難な問題が多項式時間で解ける」とは言えない。
0405◆Ph05QxAcng
垢版 |
2022/05/15(日) 03:28:07.38ID:U5FLrHO/
>>404
ありがとうございます。


ちょっとずつ問題の概要がわかってきました
0406◆Ph05QxAcng
垢版 |
2022/05/16(月) 02:52:42.35ID:C/7hB4oM
P vs NPを解くには
NP完全がPなのかそうでないのかに集約される。


今わかってる事
問題AがNP完全という条件
AがNPである事(検証だけは多項式計算量で終わる。解くのにはどれくらいかは不明)
全てのNP問題がAに多項式還元可能

そしてNP完全の問題は
彩色問題
ぷよぷよ
部分和問題
テトリス
などが存在する。

これらがPでない事を示すか、Pである事を示せば良い。

もっと抽象化してNP完全の一般的な性質を調べてみよう。
0407◆Ph05QxAcng
垢版 |
2022/05/16(月) 02:53:15.00ID:C/7hB4oM
今NP完全の問題Aが存在する。

わかっている事

AがNPである事
全てのNP問題がAに多項式還元可能

AがPかそうでないかを判定すればよい。
究極的に一般的な話だけで問題を攻略したい。

今AがPであると仮定する。(これで矛盾が導ければP!=NPである)
或いはそうでないと仮定する。その時どんな性質が出てくる？

こういう考え方は宿命の二人が一つになる方法を導いたのと全く同じような話だ。でもそっちの方が多分一般的な話をしているからそれでいいのだろうけど。


P!=NP
Pだと仮定する。
すると全てのNPはPになる。この時矛盾が生じる事を示す。１つは、この時どう足掻いてもPにならない問題の存在を示せば良い。

個人的にはこっちで話を進めて行きたい。

アルゴリズムを具体的に特定する事は難しいのであれば、宿命の二人が一つになる方法を作り上げたように純粋に言語的性質操作で出来るかもしれない。あの問題は言語の定義や性質を如何に深く理解してるかが問題を解く鍵だった。徹底した定義に対する理解の深さで知識量の多さではなかった。

NP完全の問題は沢山あるようなので最も本質に迫るには最も本質的な定義や性質をいじっていくべきな気がする。
0408◆Ph05QxAcng
垢版 |
2022/05/16(月) 02:53:35.42ID:C/7hB4oM
P=NP
Pではないと仮定すると全てのNPはPでないので、これの矛盾を示すには、どれか一つPになるNPを示せば良い。あるいはNP完全のどれか一つでも良いので多項式計算量で解ける事を示すか。

二分探索で劇的に計算量が減った事も考えよ
文字列特定は全探索のN!から二分探索でlog N!でN^2まで計算量落ちた。N!<N^Nでlog N^N=Nlog N<N^2)
これはおそらく最大の計算量と考えられるものから、多項式計算量までスリムに出来た。

N^N以上の計算量のものは存在するだろうか？


アルゴリズムの改良で減る計算量は具体的にどのくらいか考える？


全ての問題は本質的に全て同じではないか？

全ての問題がP問題ならば、全てのP問題は、本質的にある一つのP問題の変形でその問題から有限回？の変更を施せば全ての問題が得られる？

或いは逆にどのようなP問題を用意しても、本質的にNPの問題には届かない事を示す？


P!=NPならば、
PとNPを本質的に分ける何かがある筈。ある一つの属性か何かかはわからないが。

そもそも、操作が有限回の操作なわけだから、何が原因で指数計算量以上に跳ね上がるのだろうか？

P=NPではないだろうか？そうであればPとNPを本質的に分けるものはないという事だと思うが。

二分探索が使える問題は全てPに還元出来る？使えない問題はどうなんだ？

NPにばかり注目しているがPに注目するのはどうだろうか？

P=NPを示したいならPとNPが構造的に同質である事を示すのだろうか。P問題が作れられる構造とぷよぷよが論理構造の点で一対一対応している事を示すのはどうだろうか。やり方は全くわからないが。

多項式時間で解ける問題とはどういう集合だろうか。

というか、多項式とはなんだろうか？
0409◆Ph05QxAcng
垢版 |
2022/05/18(水) 03:45:46.87ID:lryA2Ixi
P=NPの場合、検証と解の特定が本当は地続きという事だろうか。

P!=NPだったらその逆か？



本の知識を勉強するより、P vs NPに関して、俺の数学理論を構築した方がいい気がする。




p vs npでわかっている情報が
問題AがNP
Aに多項式還元される

の二つしかない為皆目見当がつかないので、P=NPとP!=NPでどっちが美しい世界が広がるか、で方向性を考えるようにしたらどうだろうか。
0410◆Ph05QxAcng
垢版 |
2022/05/19(木) 03:12:32.94ID:7y75T2WL
P=NPだとして、検証の多項式の次数より解を求める次数の方が多い。何故なら暗号探索は二分探索でlog N!だが検証は一瞬だから。
0411◆Ph05QxAcng
垢版 |
2022/05/21(土) 04:41:23.40ID:Js8F1f5x
ところで検証が多項式で終わったとして、P!=NPだとしたらPとNPを分ける分水嶺があるはずだが、それは何だろうか？それがなかったらP=NPになると思うが。PとNPの境界は何だろうか？あるいはそのような検証時間や解く時間によって問題を分類する境界はなんだろうか。分類問題ではないだろうか。
0412◆Ph05QxAcng
垢版 |
2022/05/24(火) 03:13:57.47ID:hftoqFYB
もしP=NPならNPを特徴づける要素などないという事になる。
0413◆Ph05QxAcng
垢版 |
2022/05/24(火) 04:22:46.33ID:hftoqFYB
命題とはなんだろうか？
真理値が与えられるものだろうか？
コンピュータで解かれる問題は有限個の要素がある命題である。無限個あったら特定出来ない？少なくとも一生計算しても解を特定出来ない可能性がある？それでも特定出来るアルゴリズムがあるのか？
解を特定するアルゴリズムが最悪でも有界の計算量で終わる命題の集合をSolvableあるいはSと置く。ここで計算量は指数でも構わない。ここでSは特にどんな問題かは特定していない。SがPである事を示す？

Pでないと仮定する。少なくともそのような命題Aが存在したとする。
0414◆Ph05QxAcng
垢版 |
2022/05/24(火) 05:11:34.16ID:hftoqFYB
多項式と多項式より大きい最低の計算量が指数である事を示せ

大きい、の定義は、+∞の極限を取った時に((問題Aの計算量)/有限次数多項式計算量)が無限大に発散する事と定義する。
0415◆Ph05QxAcng
垢版 |
2022/05/27(金) 01:38:44.72ID:ZouYfdnC
S=Pだとしたら、もし計算量がPにならない問題があったらそもそも最初から問題が無限を扱う問題になるのか？
0416◆Ph05QxAcng
垢版 |
2022/06/02(木) 03:17:54.16ID:1VdddIY4
問題の情報量=全探索の計算量
とした場合、
二分探索による解への収束速度は2の冪乗であり、一回の試行で情報の半分が削れる。他方で、全探索のアルゴリズムは一つ一つ消していくから効率が悪い。
つまり指数収束、指数量の情報量が削れるアルゴリズムであれば、指数計算量のものでも多項式計算量に落とし込める？
0417◆Ph05QxAcng
垢版 |
2022/06/02(木) 06:42:48.36ID:1VdddIY4
二分探索をする度に2の指数乗の情報量が捨てられて行く、とすれば、情報量が問題の全探索の情報量を超えた時に解が求まる？
0418◆Ph05QxAcng
垢版 |
2022/06/05(日) 08:19:53.50ID:YyHDSuSD
指数情報量の問題のサイズに、有限回の操作で指数量の計算量を削れるアルゴリズムが存在するか否か。
0419◆Ph05QxAcng
垢版 |
2022/06/07(火) 22:56:13.01ID:QP9GQIsF
問題のサイズ(全探索の計算量)のクラス(指数量か多項式かそれ以上の計算量かの分類、計算量の型)と同じクラスの(計算量を削る)アルゴリズムが各問題について存在するか否か、を解くのと同値。この問題は美しいと思う。そして暗号に対して二分探索というアルゴリズムは存在する。美しいならば、アルゴリズムは存在してP=NPになる。
0420◆Ph05QxAcng
垢版 |
2022/06/08(水) 01:14:59.30ID:iL+HIxPa
のではないだろうか
0421１３２人目の素数さん
垢版 |
2022/06/08(水) 06:49:33.28ID:y//GtZIn
現代暗号とP≠NP予想
https://zenn.dev/senk/articles/cd8b454f14825dcaf7ec

計算複雑性にまつわる10の誤解
http://dopal.cs.uec.ac.jp/okamotoy/PDF/2013/complexity10confusions.pdf
> NP完全問題をもとにして作られた暗号 (例)
> Merkle-Hellmanのナップサック暗号系 '78
> 破られる (Shamir '84)
> その後も
> ナップサック問題(とその変種)に基づく多くの暗号系
> ほとんど破られている

> なぜ破られるのか？
> NP完全性は「最悪時」の困難性に関する概念
> 暗号は「平均時」や「ほとんどすべて」の困難性が必要
0422◆Ph05QxAcng
垢版 |
2022/06/11(土) 04:10:42.44ID:21+i4da2
>>419

命題
問題のクラスと同じクラスのアルゴリズムは存在する

と表現する方が美しい。
0423◆Ph05QxAcng
垢版 |
2022/06/16(木) 08:48:02.77ID:OdiW0Ncm
P vs Np

万物の理論に届いたのだからp=npだと思う。

命題
全ての問題に対して問題と同じクラス(型　全探索の計算量が問題の本質的型、輪郭であると思われる)のアルゴリズムが存在する

仮にある問題に対して存在しないとする。
ところが全ての根源が美である事に実数時間、有限回の操作内で届くアルゴリズムは存在すると思われる。常識的に考えれば明らかにそちらの方が大きそうだからP=Npが言えそうだ。
0424◆Ph05QxAcng
垢版 |
2022/06/16(木) 08:50:04.64ID:OdiW0Ncm
クラスが違うとnの数が大きくなると実数時間、計算量では解に届かない事になるわけで、知り得ない事がある事になる。しかし万物の理論に届いたのだから、それはなさそうだ。だからP=NPではないだろうか。
0425◆Ph05QxAcng
垢版 |
2022/06/16(木) 08:53:38.83ID:OdiW0Ncm
つまり、知るには無限大超実数時間いる問題が必要になるかもしれないが、万物の理論的にはそれはなさそうだから。
0426◆Ph05QxAcng
垢版 |
2022/06/16(木) 09:02:29.11ID:OdiW0Ncm
同じクラスのアルゴリズムがないと仮定すると、解に辿り着くまで無限大超実数に限りなく近づける。つまり、全ての問題が解けるわけではないが、全ての問題に因果関係があるのであればそのセンは薄そうだ。
0427◆Ph05QxAcng
垢版 |
2022/06/18(土) 01:37:37.25ID:AYGMEa0q
もし問題と同じクラスのアルゴリズムがなかったら、知り得ない事があると言う事になりそうだが、万物の理論で全て解明されるのであればそれは背理ではないだろうか。こういう論法が数学で認められるかは別にして、大まかな方針を立てる上では役に立つのではないだろうか。
0428◆Ph05QxAcng
垢版 |
2022/06/26(日) 13:40:19.30ID:yayuGS8J
p vs np
全てを有限時間内で知る事は出来ない→万物の根源は知る事が出来ない、となる？

万物の根源=無矛盾性

そもそも人間の抽象化とコンピュータによる計算は異なるからこれは成り立たない？
0429◆Ph05QxAcng
垢版 |
2022/07/26(火) 00:15:21.26ID:L+mB4KqR
a flood of circle 花火を見に行こうぜ
夢が叶うのは奇跡ではない、手が届くように空間は曲がっている
というのが佐々木亮介氏の主張だが、この主張が真理ならばP=NPではないだろうか。
そもそも最大の計算量の問題はなんだろうか。それが実数時間で解けたら全ての問題は実数時間で解けるになると思われるが。推測では無矛盾性をどうやって示すか、になりそうだが。
0430◆Ph05QxAcng
垢版 |
2022/07/27(水) 00:05:04.29ID:u20S6rjn
問題と同じクラスのアルゴリズムが存在する
という命題はP=NPの拡張、一般化である、と思われる。

これが真でないとすると、この世界が無矛盾である事を実数時間で解く事は出来ないと思う。

表現を変えるならば、不可能はない。

問題と同じクラスのアルゴリズムが存在する
という命題は非常に深い問題だ。何故なら全ての問題は実数時間で解ける事を意味するからだ。数学的にも哲学的にも。

即座に数学的証明が出来なくても、哲学的、言語的証明が出来た後で思考を深め洗練させれば数学的証明も出来ると思う。
0431◆Ph05QxAcng
垢版 |
2022/07/27(水) 00:24:20.11ID:6h9qLQbD
この命題の表現を変えると
全ての問題は実数時間内で解ける
になると思う。
もし仮に実数時間内で解けない命題があると、それは無矛盾性に反するのではないだろうか。とすると矛盾するから全ての命題は実数時間内で解ける事になり、
全ての問題に対して問題と同じクラスのアルゴリズムは存在する
は示されたような気はするがまだ何処か穴はあるだろうか。
0432◆Ph05QxAcng
垢版 |
2022/07/27(水) 00:27:18.83ID:tYMBVVOW
あーダメだ、また失敗した
0433◆Ph05QxAcng
垢版 |
2022/07/27(水) 00:29:08.42ID:1jccA0Ci
多分、実数時間内で解けて、かつその時間は上界があり+∞に発散する事はない、事を示さないといけないのか
0434◆Ph05QxAcng
垢版 |
2022/07/30(土) 02:14:02.80ID:EKvEmpQ+
予想:計算可能な問題(計算量が有限な問題)に対して問題と同じクラスのアルゴリズムが存在する

をさらに拡張すると

全ての命題に対して問題と同じクラスのアルゴリズム、解が存在する
は真か否か→連続体仮説から言えば偽かもしれないが、どちらでもない、も解に含めた場合、真実ではないか？
0435◆Ph05QxAcng
垢版 |
2022/07/30(土) 23:07:25.79ID:12zK5snW
「解ける」ってどういう事なのか。四色問題、ケプラー予想はコンピュータによって解かれたが、超実数時間がかかるなら解けたと言うのだろうか→言わない
少なくともp vs npでは言わない。多項式で計算量が抑えられるという意味だ。
0436◆Ph05QxAcng
垢版 |
2022/07/31(日) 01:05:28.58ID:8ndntkI7
命題が解ける、とは
命題が真か偽か判定不能か分類わけが出来る、と定義する、のだろうか。少なくとも問題がどういう状況か完全に判別されている状況を指すと思われる。
0437１３２人目の素数さん
垢版 |
2022/08/01(月) 23:10:43.78ID:dHWXTxuI
笑わない
0438１３２人目の素数さん
垢版 |
2022/08/03(水) 21:05:00.31ID:p5gFyYJI
２３：０５からNHKで「笑わない数学」。
今日は「P対NP問題」だ。
0439◆Ph05QxAcng
垢版 |
2022/08/04(木) 23:37:09.36ID:HSqZUK0F
見れなかったですね
0440◆Ph05QxAcng
垢版 |
2022/08/23(火) 23:01:34.01ID:nlEjhniO
最小のアルゴリズムは必要十分な解答である。つまり問題の設定から導かれる。
と予想されるが正しいか？反例はないか？

全探索は十分条件。二分探索は必要十分？
全探索は解よりももっと大きな計算を行う→十分条件
必要十分の解法は設定そのものに対するアプローチ？

解とそれ以外の候補の外見、条件が対称で見分けがつかない。
0441１３２人目の素数さん
垢版 |
2022/08/23(火) 23:50:22.55ID:mQgVP0hh
証明が存在したとしても、その記述の長さの最小数が宇宙の原子の数よりも
大きかったなら、証明は記述し終えることはできない。
つまり証明可能であったとしても実際にそれを読み尽くすことができないのだ。

巡回ハミルトン路の存在判定の問題も、たとえばグラフを隣接行列で
表してやれば、それは可付番であるから、グラフｇに対して自然数ｎを
対応させる写像ｆが存在する。そうして、いま無限長の二値配列Aであって、
グラフｇにハミルトン路があるなしによって配列の要素A[f(g)]の値として
1と0が入って居る、そのような配列Aが存在する。
すると、グラフｇが任意に与えられたときn=f(g)を計算する。
この計算は多項式時間でできるだろう。
そうして配列Aのｎ番目の要素をO(1)の計算量で取り出すと、
グラフｇがハミルトン路を持てば1であり、そうでなければ0なのであるから、
結局ハミルトン路の存在判定は多項式時間で可能になるのだ。
＃ただし、配列Aを具体的に構成することはおそらく多項式時間では
できないのだと思う。配列の要素数が無限大ではナンセンスだという
批判もありうるだろうが、かりにf(n)の値がある上限N以下になる
ようなグラフに対してだけ判定を行えば良いのならば、配列Aの要素数は
有限N＋1個で良くなるだろう。
0442◆Ph05QxAcng
垢版 |
2022/08/28(日) 22:14:15.83ID:IdSjnm0+
>>441
僕に対するコメントですか？
0443１３２人目の素数さん
垢版 |
2022/09/05(月) 09:45:07.88ID:RYy03OiT
もしも理想的な量子計算機があって、そのような計算機上ではN=NPになるのならば、
通常のN=NPであるか？という問いは、何かの仮定が欠けている設問なのかもしれない。
0444１３２人目の素数さん
垢版 |
2022/10/19(水) 12:38:26.67ID:PC0a3RIi
証明ができたら僕の購読している数セミにぜひとも投稿して下さい。
0445１３２人目の素数さん
垢版 |
2022/10/20(木) 11:26:18.69ID:nC8yZw8K
>>443
「オラクル」があれば或る意味NP困難でもPで確率論的には解けるんじゃなかったっけ？
0446１３２人目の素数さん
垢版 |
2022/10/20(木) 17:39:48.74ID:BFQZM8qc
問題の出題者が答えを知っている場合には、
出題者を攻略して答えを聞き出すのが手間が少ない場合がある。
おとなしく応じなければ、拷問したり、
あるいはもっと紳士的に自白剤を使うとか。
将来は脳内電磁信号をニューラルネットで解析することにより、
暴力や薬物を使わずに、脳内の記憶を引きだすことができる
ようになるかもしれないな。
困難な20文字からなるパスワードもソフトあるいは
ハードでクラックするのではなくて、ユーザー自身に
その意志に反してでも語らせれば良いのだ。
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況