P vs NP
■ このスレッドは過去ログ倉庫に格納されています
描
>14 名前:132人目の素数さん :2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間。
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>
> 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 描
>14 名前:132人目の素数さん :2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間。
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>
__ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ ふむ、見たところnが2倍になるごとにケタが3つ上がっとるだけやナ
これやったらn^11で足りるナ 描
>14 名前:132人目の素数さん :2012/08/07(火) 17:39:00.96
> >>13
> 旧コテ猫あらため描つまりお前自身の事だろ、増田哲也に限り無く近い人間。
> 筑波大学で痴漢と言えば増田哲也だから連続性も明らかになってるから
> わざわざ限り無く近い人間なんて呼び方しなくていいんだけどな
>
__ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/ 過疎ってるようなので質問お願いします
群の定義は「演算が閉じること」「結合則が成り立つこと」「どの元にも逆元が
存在すること」「単位元が存在すること」の4つですが、単純群の分類理論を
用いずに、この定義だけからある位数nの群全てを見つけようとするとそれは
NPになってしまう、という理解は正しいですか?
単位元を用意して、逆元とペアになった2つの元か自分自身が逆元である1つの
元を順次加えていっても結合則の保証や演算が閉じることの保証はできません。
もし演算が閉じることや結合則が必要なければPで解くことができて、演算が閉じる
ことや結合則のような集合に対する「縛り」でしかないものを解こうとするとNPに
なってしまう、という理解で正しいでしょうか?
ご指導お願いします nが与えられたときに具体的にどういう出力を返す問題の事を言っているのか分からない。
それぞれの群ごとにn^2の演算表を全部出力するの?
それとも例えば生成元と基本関係式で答えたり行列を用いて表現したりするの?
いずれにせよ、NPというのはyesかnoで応えられるような問題で、
しかも答えが実際に与えられたときに、その答えが本当に正しいかどうかを
多項式時間で判定できるような問題だということなんだけど、
たぶんあなたの考えているような問題はNPですらないんじゃないだろうか。
まずはPとNPの定義くらい確認したらどうだろう むしろDTMとNTMの定義を読んでこういうことかな?と思って質問したのですが...
得られる結果をどういうデータ構造で格納するかによって問題の種類が変わりますか?
欲しい出力は与えられた位数nの群全てを何らかのデータ構造で格納したものです 演算表で出力するなら
位数nの群m個を表示するのにn^2mの長さの出力が要るじゃん
他のNP問題でそんなバカでかい出力を要する問題見たことないよ
というかそれ以前にNPもPもyes/noで応えられる決定問題のクラスらしいよ yes/noで答えるために何をしなければならないか、あるいはどんなマシンでないと
多項式時間で解けないか、ですよね? __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ ∧,,,∧
( ・∀・) ほー それで
( : )
し─J
__ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/
. | \ ∠イ ,イイ| ,`-' | このスレ、レス数がやや少ないので上げとくわね。
| l^,人| ` `-' ゝ |
| ` -'\ ー' 人
| /(l __/ ヽ、
| (:::::`‐-、__ |::::`、 ヒニニヽ、
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/ NP困難問題である巡回セールスマン問題は多項式時間で解けそうだ。 __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/ __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。
. | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。
| l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。
| ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて
| /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。
| (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は?
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら?
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/ __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/
. | \ ∠イ ,イイ| ,`-' |
| l^,人| ` `-' ゝ | このスレは馬と鹿と豚さんばかりね。
| ` -'\ ー' 人
| /(l __/ ヽ、
| (:::::`‐-、__ |::::`、 ヒニニヽ、
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/ __ノ)-'´ ̄ ̄`ー- 、_
, '´ _. -‐'''"二ニニ=-`ヽ、
/ /:::::; -‐''" `ーノ
/ /:::::/ \
/ /::::::/ | | | |
| |:::::/ / | | | | | |
| |::/ / / | | || | | ,ハ .| ,ハ|
| |/ / / /| ,ハノ| /|ノレ,ニ|ル'
| | | / / レ',二、レ′ ,ィイ|゙/
. | \ ∠イ ,イイ| ,`-' |
| l^,人| ` `-' ゝ | このスレには馬と鹿と豚さんしかいないのね。
| ` -'\ ー' 人
| /(l __/ ヽ、
| (:::::`‐-、__ |::::`、 ヒニニヽ、
| / `‐-、::::::::::`‐-、::::\ /,ニニ、\
| |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \
. | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \
| /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 |
| |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、
| |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄|
| /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_|
| |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
| /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/ NP=PならP=NP=NP=P とならないならP=NPとはならない
ミレニアム問題の1つ解決 >>28
1*2=2
2=1*2=1*2=2
というP=NPならP vs NPは否定される >>29
Nを1の集合Pは2の集合とすると
2に1を幾らかけ算しても2
2進法か3進法ならP vs NPは否定される このスレの人なら知っているかもしれないんで聞きます。
山口人生博士って、どうやって生計を立てているんですか。 >>1
これ問題自体がおかしいだろ
そもそも
より計算量の少ないアルゴリズムが存在したところで
そのアルゴリズムを見つけるために要した時間は
どこに消えちゃうのさ?
さらに、存在しないなんてのを見つけろなんて言う問題は
悪魔の証明だよ? 低レベルなレスばかりだな。
P vs NP問題の定義が分かっていれば、出て来ないような意見ばかりだ。
アホ過ぎ。 多項式時間以内に収まる最短経路が存在するかどうかの問題
何かの数学上の系において
ある問題=拘束条件を与えた時
多項式時間以内に収まるアルゴリズムが存在する場合に
その出力が問題の解に含まれるかを確認できる
多項式時間以内に収まる経路が存在するかどうか
系が与える前提あるいはルールと問題が与える拘束条件
さらにこれらが生成するさまざまな経路が存在し得るんだけど
一番短い経路は多項式時間以内に収まりますか?
最悪集合全部を読み上げてそれに含まれるかを調べればよい
だが系の定義によって同値ではなく一方向や非可逆な経路とかもあって
その場合は最初からすべて生成してみないことにはわからないことがある
あるいは別経路で到達可能かを探さないといけないわけだが
それはそれで総当り戦になるし、そういう経路がいくつあるのかも
生成して読みあげてみないとわからない
人間が試してたまたまうまくいくのを探し当てられたらそれはP=NP問題
んで、すべてのP問題についてさらにこれら上記をもう一度やるという問題
すべてのP問題を生成しなくても何らかの別経路で証明=到達出来ればよいが・・・
それには問題を再定義しないといけないな
最悪多項式時間以内に収まるPアルゴリズムが存在する問題の集合をすべて生成してもいいけどさw それって多項式時間以内に収まるか?という再帰問題になるぜ?w >>33
より計算量の少ないアルゴリズムが存在したらそれはええことやないか。それともあかんのか 一次従属とかを直接扱えるCPUがあったらぜひプログラミングしてみたい P vs NP問題を解決するとされている、「消滅解」って、
具体的にどういうものか知っている人いますか。 山口人生氏の本を読んだけど、本に記されている記述が不十分なのか、私の理解力が不十分なのか分りませんが、
読んでも結局分りませんでした。 ■ このスレッドは過去ログ倉庫に格納されています