TOP カテ一覧 スレ一覧 100〜終まで 2ch元 削除依頼
\section{TeX の時間} %%% 第 XI 節 %%% Part.2
数学板の天才方、表現論の教科書教えてください 数論方面で
現代数学など社会ではなんの役に立たない
くだらねぇ問題はここへ書け
面白い問題おしえて〜な 32問目
ラマヌジャン、ってナニモノ?
京大生以外は数学語るな
馬鹿「大学の数学は哲学みたいなもの」
分からない問題はここに書いてね445
数学の本 第83巻
P vs NP
- 1 :2012/08/13 〜 最終レス :2018/07/12
- http://en.wikipedia.org/wiki/P_versus_NP_problem
- 2 :
- 描
>14 名前:132人目の素数さん :2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間。
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>
- 3 :
- > 363 自分:132人目の素数さん[sage] 投稿日:2012/08/12(日) 21:39:21.60
> 質問です
> 例えば群であれば、ある位数nの群すべてを多項式時間で見つけ出す
> アルゴリズムは存在しているといえるのですか?
>
> 364 名前:132人目の素数さん[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
- 4 :
- 描
>14 名前:132人目の素数さん :2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間。
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>
- 5 :
- __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
- 6 :
- ふむ、見たところnが2倍になるごとにケタが3つ上がっとるだけやナ
これやったらn^11で足りるナ
- 7 :
- 描
>14 名前:132人目の素数さん :2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間。
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>
- 8 :
- __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
- 9 :
- 過疎ってるようなので質問お願いします
群の定義は「演算が閉じること」「結合則が成り立つこと」「どの元にも逆元が
存在すること」「単位元が存在すること」の4つですが、単純群の分類理論を
用いずに、この定義だけからある位数nの群全てを見つけようとするとそれは
NPになってしまう、という理解は正しいですか?
単位元を用意して、逆元とペアになった2つの元か自分自身が逆元である1つの
元を順次加えていっても結合則の保証や演算が閉じることの保証はできません。
もし演算が閉じることや結合則が必要なければPで解くことができて、演算が閉じる
ことや結合則のような集合に対する「縛り」でしかないものを解こうとするとNPに
なってしまう、という理解で正しいでしょうか?
ご指導お願いします
- 10 :
- nが与えられたときに具体的にどういう出力を返す問題の事を言っているのか分からない。
それぞれの群ごとにn^2の演算表を全部出力するの?
それとも例えば生成元と基本関係式で答えたり行列を用いて表現したりするの?
いずれにせよ、NPというのはyesかnoで応えられるような問題で、
しかも答えが実際に与えられたときに、その答えが本当に正しいかどうかを
多項式時間で判定できるような問題だということなんだけど、
たぶんあなたの考えているような問題はNPですらないんじゃないだろうか。
まずはPとNPの定義くらい確認したらどうだろう
- 11 :
- むしろDTMとNTMの定義を読んでこういうことかな?と思って質問したのですが...
得られる結果をどういうデータ構造で格納するかによって問題の種類が変わりますか?
欲しい出力は与えられた位数nの群全てを何らかのデータ構造で格納したものです
- 12 :
- 演算表で出力するなら
位数nの群m個を表示するのにn^2mの長さの出力が要るじゃん
他のNP問題でそんなバカでかい出力を要する問題見たことないよ
というかそれ以前にNPもPもyes/noで応えられる決定問題のクラスらしいよ
- 13 :
- yes/noで答えるために何をしなければならないか、あるいはどんなマシンでないと
多項式時間で解けないか、ですよね?
- 14 :
- >>12
なんなら出力は群の個数にします?
- 15 :
- おやすみー
- 16 :
- うざ
- 17 :
- そそるな
- 18 :
- __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
- 19 :
- , '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
- 20 :
- 私はP=NPだと考えています。
- 21 :
- ∧,,,∧
( ・∀・) ほー それで
( : )
し─J
- 22 :
- __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/
. | \ ∠イ ,イイ| ,`-' | このスレ、レス数がやや少ないので上げとくわね。
| l^,人| ` `-' ゝ |
| ` -'\ ー' 人
| /(l __/ ヽ、
| (:::::`‐-、__ |::::`、 ヒニニヽ、
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
- 23 :
- NP困難問題である巡回セールスマン問題は多項式時間で解けそうだ。
- 24 :
- __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
- 25 :
- __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
- 26 :
- __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/
. | \ ∠イ ,イイ| ,`-' |
| l^,人| ` `-' ゝ | このスレは馬と鹿と豚さんばかりね。
| ` -'\ ー' 人
| /(l __/ ヽ、
| (:::::`‐-、__ |::::`、 ヒニニヽ、
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
- 27 :
- __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/
. | \ ∠イ ,イイ| ,`-' |
| l^,人| ` `-' ゝ | このスレには馬と鹿と豚さんしかいないのね。
| ` -'\ ー' 人
| /(l __/ ヽ、
| (:::::`‐-、__ |::::`、 ヒニニヽ、
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
- 28 :
- NP=PならP=NP=NP=P とならないならP=NPとはならない
ミレニアム問題の1つ解決
- 29 :
- >>28
1*2=2
2=1*2=1*2=2
というP=NPならP vs NPは否定される
- 30 :
- >>29
Nを1の集合Pは2の集合とすると
2に1を幾らかけ算しても2
2進法か3進法ならP vs NPは否定される
- 31 :
- p
- 32 :
- このスレの人なら知っているかもしれないんで聞きます。
山口人生博士って、どうやって生計を立てているんですか。
- 33 :
- >>1
これ問題自体がおかしいだろ
そもそも
より計算量の少ないアルゴリズムが存在したところで
そのアルゴリズムを見つけるために要した時間は
どこに消えちゃうのさ?
さらに、存在しないなんてのを見つけろなんて言う問題は
悪魔の証明だよ?
- 34 :
- 低レベルなレスばかりだな。
P vs NP問題の定義が分かっていれば、出て来ないような意見ばかりだ。
アホ過ぎ。
- 35 :
- 多項式時間以内に収まる最短経路が存在するかどうかの問題
何かの数学上の系において
ある問題=拘束条件を与えた時
多項式時間以内に収まるアルゴリズムが存在する場合に
その出力が問題の解に含まれるかを確認できる
多項式時間以内に収まる経路が存在するかどうか
系が与える前提あるいはルールと問題が与える拘束条件
さらにこれらが生成するさまざまな経路が存在し得るんだけど
一番短い経路は多項式時間以内に収まりますか?
最悪集合全部を読み上げてそれに含まれるかを調べればよい
だが系の定義によって同値ではなく一方向や非可逆な経路とかもあって
その場合は最初からすべて生成してみないことにはわからないことがある
あるいは別経路で到達可能かを探さないといけないわけだが
それはそれで総当り戦になるし、そういう経路がいくつあるのかも
生成して読みあげてみないとわからない
人間が試してたまたまうまくいくのを探し当てられたらそれはP=NP問題
んで、すべてのP問題についてさらにこれら上記をもう一度やるという問題
すべてのP問題を生成しなくても何らかの別経路で証明=到達出来ればよいが・・・
それには問題を再定義しないといけないな
最悪多項式時間以内に収まるPアルゴリズムが存在する問題の集合をすべて生成してもいいけどさw それって多項式時間以内に収まるか?という再帰問題になるぜ?w
- 36 :
- >>33
より計算量の少ないアルゴリズムが存在したらそれはええことやないか。それともあかんのか
- 37 :
- 一次従属とかを直接扱えるCPUがあったらぜひプログラミングしてみたい
- 38 :
- 玉石混淆スレあげ
- 39 :
- 平叙文と命令文が等価ならプログラマ全員失業やがな
- 40 :
- 山口人生氏の本を読んだけど、本に記されている記述が不十分なのか、私の理解力が不十分なのか分りませんが、
読んでも結局分りませんでした。
- 41 :
- 分かったら数学続けられんよ
- 42 :
- PvsNPってイエスかノーで答えられる判定問題だけを扱うんだよね
P=NPだとしたらRSA暗号が簡単に解読できる方法があることになるからヤバいって話をよく聞くけど、ある数の素因数を求めよって問題は判定問題じゃないから、PやNPとは何も関係ないんじゃね?
- 43 :
- >>42
NがM未満の素因数を持つか?っていう決定問題がPだと、二分探索をその桁数のオーダーだけやれば解けちゃうよ
- 44 :
- >>42
>>42だが納得しました
- 45 :
- P/NP=N^(-1)
- 46 :
- http://peace.2ch.sc/test/read.cgi/tech/1407367226/379,382,384,386
- 47 :
- みきやん予想
ある位数nの群全てを多項式時間で見つけ出すアルゴリズムは存在する
- 48 :
- すみません、計算機屋のみきやんですけど反応ください
- 49 :
- 改定
みきやん予想
任意の位数nの群全てを多項式時間で見つけ出すアルゴリズムは存在する
- 50 :
- NP≠Pを証明するのってなんでそんなに難しいの?
- 51 :
- 問題の汎用性が高いからかなぁ
俺もよくわからん
- 52 :
- P ≠ NP を自力で証明することと
P ≠ NP 予想を誰かが解決したあとにその照明の内容を理解することはどちらが難しいか?
- 53 :
- 入門書読むと、コンピュータ科学最大の難問の一つである、とか証明の努力を退けてきた、とか
いろいろ書いてあるけど、どういう試みがなされたのかとか証明につながるヒントとか
可能性がたかそうなルートとか研究の中途の説明ってないんだよねえ
誰か教えてよ
進展具合とか、もうみんな諦めちゃって手がついていないのか?
- 54 :
- 自力で証明する方が難しいに決まってるだろ
- 55 :
- >>54 証明せよ
- 56 :
- まあ、俺以外の誰かだと500年くらい掛かりそうだが、俺なら200年で出来る気がするな
人生短いから、実証出来ないのが残念
- 57 :
- 自力で証明する方が証明のチェックより難しいというのは
まさにP ≠ NP的な話だね
- 58 :
- 人工知能にNP問題学習させたら多項式時間で解けるようなったりして。
- 59 :
- >>58
人工知能もNPも理解してなさそうだな
- 60 :
- >>59
指摘があるなら具体的に頼む。
- 61 :
- >>58に具体性のかけらもないのに?
- 62 :
- TSPの都市配置と最短経路を学習データとして
ディープラーニングで学習させたら良い解返してくれるんじゃないか。
- 63 :
- >>62
わりといい近似解が出ることを、「とける」とは言わない
- 64 :
- CNFと充足解を学習データとして
ディープラーニングで学習させたらSATが多項式時間で解けるようになるかも
まあSATは無理でも素因数分解とかなら良い線いくんちゃう?
- 65 :
- どうでもいい与太話も結構だが、君は「解ける」の意味をちゃんと理解してから書き込むように
- 66 :
- 導出原理なかなか楽しい。
鳩ノ巣原理なんかは時間かかるらしいが。
- 67 :
- すまん、だれか教えてくれ
http://www.ti.inf.ethz.ch/ew/lehre/extremal04/raemy.pdf
これなんだが。
なぜサイズmの鳩ノ巣原理のレゾリューションの証明の中に
m^2/9個の変数を持つクローズが出てくることが言えると、
鳩ノ巣原理の証明長が指数になることが言えるの?
m^2/9個の変数を持つクローズが全部出てくるの?
- 68 :
- 記述計算量において、
Pは「最小不動点演算子を持つ一階述語論理」で、
NPは「存在量化二階述語論理」であらわされる。
「最小不動点演算子を持つ一階述語論理」の無矛盾性を
「存在量化二階述語論理」で証明できれば、
ゲーデルの第二不完全性定理より、
「最小不動点演算子を持つ一階述語論理」より
「存在量化二階述語論理」が大きいと言えるから、
P≠NPも言えるのではないか。
この証明、どうだろう?
- 69 :
- 無矛盾性ってどうやって証明するのん?
- 70 :
- 述語論理の公理系の規則が全てトートロジーである事から証明できると思います。
- 71 :
- たとえばP vs NP が連続体仮説の結果に依存するとかいう可能性はあるの?
- 72 :
- あるいはビジービーバーみたいにNPを多項式で解くアルゴリズムは存在することはするけど、
どのアルゴリズムがそれかは絶対わからないとか。
- 73 :
- あ
- 74 :
- 俺が証明したらフィールズ賞くれるの?
- 75 :
- ¥
- 76 :
- ¥
- 77 :
- ¥
- 78 :
- ¥
- 79 :
- ¥
- 80 :
- ¥
- 81 :
- ¥
- 82 :
- ¥
- 83 :
- ¥
- 84 :
- ¥
- 85 :
- ¥
- 86 :
- ¥
- 87 :
- ¥
- 88 :
- ¥
- 89 :
- ¥
- 90 :
- ¥
- 91 :
- ¥
- 92 :
- ¥
- 93 :
- ¥
- 94 :
- ¥
- 95 :
- ¥
- 96 :
- いきなりすまん。
解けたけど、(自分以外)だれも理解できないっぼい。
ペレルマンさんの気持ちがわかる気がする。
- 97 :
- フィールズ賞もらえる歳は超えちまった。
ちなみに、フィールズ賞(ノーベル賞もだけど)は税金がかからんが、
クレイ研究所が提示してる方は免除の記載が無いらしいので、
このままだと半分が税金。
- 98 :
- ¥
- 99 :
- ¥
- 100 :
- ¥
100〜のスレッドの続きを読む
ポエムはここに書いてね 2
現代数学の系譜 工学物理雑談 古典ガロア理論も読む82
不等式への招待 第10章
小学校のかけ算順序問題×19
名古屋】有限会社モトミ食品輸送【トランストラスト2】
(・ω・)俺が日々の数学的発見を書くスレ
数理論理学(数学基礎論) その12
7777で10作れる奴いんの?
1文字変えたら難易度が激変する問題 3文字目
■■■■■■■■■■■■■ 人工太陽
--------------------
井上バレエ団
実況パワフルプロ野球2016 応援歌スレ Part1
●◇ 天ぷらうどんは邪道ではないのか? ◇●
刃物板オリジナルナイフとか作れねえかな?
【表現の不自由展・再開】 鑑賞者は事前に「教育プログラム」実施 鑑賞中は監視役付き 金属探知機によるチェックも★2
2文字限定しりとり Part31
☆高血圧を語ろう・106 ★ワッチョイ★
【LoL】League of Legends 1605LP【IPあり】
低脳するーするんとウスラバカルンペン武雄とキチガイねえねえ爺を生暖かく見守る優しいスレ…25ウスラバカ
00の水島ってダメな方の水島と言われてるらしいな
【腐女子カプ厨】ホモ水泳雑談1595【なんでもあり】
ゴッドタン【第6回腐り芸人セラピー】
平和村
【2356】TCBホールディングス
海外ではトレイルランが賞賛されてるのに日本では
日テレ、パク・キョンベ容疑者出演「今日から俺は!!」代役・やべきょうすけで撮影し直し
発達障害者と定型発達の人との質問交流場☆9
【PS4】ウイイレ2018 チームプレー WELスレ Part2
【やっぱ】7枚合板ラケットスレ【木材でしょ】
【FF14】超絶お嬢様れいちスレ【腕毛】
TOP カテ一覧 スレ一覧 100〜終まで 2ch元 削除依頼