P=NP証明猿 Part2
932 ：１３２人目の素数さん：01/12/21 18:58
http://www.ipsj.or.jp/katsudou/taikai/64taikai.html
第６４回全国大会
高度情報通信ネットワーク社会を目指す産・官・学の共演
会期：平成１４年３月１２日（火）〜１４日（木）
会場：東京電機大学鳩山キャンパス
第６４回全国大会
高度情報通信ネットワーク社会を目指す産・官・学の共演
会期：平成１４年３月１２日（火）〜１４日（木）
会場：東京電機大学鳩山キャンパス
933 ：１３２人目の素数さん：01/12/21 19:06
>932
じ、人生短はどこ？（ｗ
じ、人生短はどこ？（ｗ
934 ：１３２人目の素数さん：01/12/21 19:48
素朴な疑問。
神帝は>>865で
＞具体的には、従来は、Ｐ＝ＮＰの証明は、早いアルゴリズムを見つけることで証明するものだと、皆信じていた。
＞ところが、そうじゃなかったという事実を、かの、山口人生大天才が指摘したわけだ。
と言っている。ここで､山口先生が自らのホームページで言うように
＞というよりも、Ｂ（ｍ）-ＳＡＴ全体をクラス分けして、Ｐになるクラスを取り出す。
＞これを、今、ＰＢＳと名付けましょう。
＞ポイントは、ＳＡＴがＰでＰＢＳに還元できるという事実です。
であるならば､山口先生の証明の基本論法はきわめて伝統的で､
（１）PBSが多項式時間で解けることと､
（２）SATからPBSへの変換が多項式時間でできることの
両方を示した､というだけである。この基本論法じたいは誠に常識的かつ基礎的かつ単純で､
画期的でもなんでもない。
すると､山口先生の画期的なところは､（１）と（２）の両方あるいはいずれかについて
具体的アルゴリズムを示さずに多項式時間で解けることを示したところにあるはずだが､
（１）はもともと多項式時間で解けるクラスを選んだだけだから､（２）を画期的な方法で
アルゴリズムを示さずに解いたのだろうと推定される。
しかし､多項式時間で解けるという結論が一旦得られたからには､SATをPBSへ変換する多項
式時間アルゴリズムを具体的に示すことに､いったいどんな困難があるのであろうか？
そこが非常に疑問である。できないとすれば､それはとても不自然なことである。
まさか､P=NPでないと困るから多項式時間でできることにしたらP=NPが結論できた､
というのではあるまいな。
神帝は>>865で
＞具体的には、従来は、Ｐ＝ＮＰの証明は、早いアルゴリズムを見つけることで証明するものだと、皆信じていた。
＞ところが、そうじゃなかったという事実を、かの、山口人生大天才が指摘したわけだ。
と言っている。ここで､山口先生が自らのホームページで言うように
＞というよりも、Ｂ（ｍ）-ＳＡＴ全体をクラス分けして、Ｐになるクラスを取り出す。
＞これを、今、ＰＢＳと名付けましょう。
＞ポイントは、ＳＡＴがＰでＰＢＳに還元できるという事実です。
であるならば､山口先生の証明の基本論法はきわめて伝統的で､
（１）PBSが多項式時間で解けることと､
（２）SATからPBSへの変換が多項式時間でできることの
両方を示した､というだけである。この基本論法じたいは誠に常識的かつ基礎的かつ単純で､
画期的でもなんでもない。
すると､山口先生の画期的なところは､（１）と（２）の両方あるいはいずれかについて
具体的アルゴリズムを示さずに多項式時間で解けることを示したところにあるはずだが､
（１）はもともと多項式時間で解けるクラスを選んだだけだから､（２）を画期的な方法で
アルゴリズムを示さずに解いたのだろうと推定される。
しかし､多項式時間で解けるという結論が一旦得られたからには､SATをPBSへ変換する多項
式時間アルゴリズムを具体的に示すことに､いったいどんな困難があるのであろうか？
そこが非常に疑問である。できないとすれば､それはとても不自然なことである。
まさか､P=NPでないと困るから多項式時間でできることにしたらP=NPが結論できた､
というのではあるまいな。
935 ：( ´_ゝ`)ﾌｰﾝ｡o0○【( ﾟДﾟ)凸】 ：01/12/21 23:58
散歩しにわざわざ逝って、なにえらそうに書いてんだか。
小物だねぇ。ｶﾞｶｰﾘしたよ。
小物だねぇ。ｶﾞｶｰﾘしたよ。
936 ：１３２人目の素数さん：01/12/22 01:06
937 ：１３２人目の素数さん：01/12/22 01:27
＞どう思います？ ┤
今日，忘年会．すげー酔っ払ってハッピー．
以上．
今日，忘年会．すげー酔っ払ってハッピー．
以上．
938 ：１３２人目の素数さん：01/12/22 01:33
でもこのスレが賑わうひとつには、人生の資産と高学歴に
妬む人間が多いからだろうな。
高卒のＤＱＮ企業社長がこれをやっても、ここまで盛況には
ならんだろうな。
なんのかんの言っても、人生はやっぱり勝ち組みか。
妬む人間が多いからだろうな。
高卒のＤＱＮ企業社長がこれをやっても、ここまで盛況には
ならんだろうな。
なんのかんの言っても、人生はやっぱり勝ち組みか。
939 ：１３２人目の素数さん：01/12/22 01:39
人生、大学やめさせられたんだっけ？
940 ：１３２人目の素数さん：01/12/22 02:19
>>938
このスレで得られた教訓
「人間，金と思い込み(妄想？)があれば幸せに生きられる」
ってことでしょ？（笑）
勝ち組みと言うか，あの状況で自分が勝ち組みだと思える妄想力
が皆の関心(反感？)を呼び起こすんじゃないでしょうか？
このスレで得られた教訓
「人間，金と思い込み(妄想？)があれば幸せに生きられる」
ってことでしょ？（笑）
勝ち組みと言うか，あの状況で自分が勝ち組みだと思える妄想力
が皆の関心(反感？)を呼び起こすんじゃないでしょうか？
941 ：１３２人目の素数さん：01/12/22 03:55
はー……この程度の学歴なら周りにゴロゴロいるが。
数学板の住人なら入院以上が普通だし。
彼の妄想というか想像力とストーリーテリングは“それなりに”すごいね。
別な方向へ活かしてれば、“それなりに”成果を残せる人だとは思う。
でも、結局彼の遺したものは、ブーリアンテストにP=NP（脳内）……。
数学板の住人なら入院以上が普通だし。
彼の妄想というか想像力とストーリーテリングは“それなりに”すごいね。
別な方向へ活かしてれば、“それなりに”成果を残せる人だとは思う。
でも、結局彼の遺したものは、ブーリアンテストにP=NP（脳内）……。
942 ：１３２人目の素数さん：01/12/22 04:15
>>837
なんとなく言ってるんですが、イリノイ大学の4色問題の
証明は、P つまりP=NPだったってことなんですか？
途方も無いくらい時間のかかる問題を、工夫してすばやくといてしまった
とかどーとか耳にしたことがあります。
これは全然関係ないんでしょうか？
あとP=NPの証明がP=NP問題だったなんてこともあるのかな？
全然分かって無くて、なんとなく言ってるだけなんで
凄く見当違いのこと言ってるかもしれません。
なんとなく言ってるんですが、イリノイ大学の4色問題の
証明は、P つまりP=NPだったってことなんですか？
途方も無いくらい時間のかかる問題を、工夫してすばやくといてしまった
とかどーとか耳にしたことがあります。
これは全然関係ないんでしょうか？
あとP=NPの証明がP=NP問題だったなんてこともあるのかな？
全然分かって無くて、なんとなく言ってるだけなんで
凄く見当違いのこと言ってるかもしれません。
943 ：１３２人目の素数さん：01/12/22 08:15
>941
「入院」というのは、語弊があるような。
大学院卒（院生）っぽい人たちが多いのは確かだ。
「入院」というのは、語弊があるような。
大学院卒（院生）っぽい人たちが多いのは確かだ。
944 ：１３２人目の素数さん：01/12/22 09:32
次スレ立てますかねー？ 本家のP=NPは脳内ということで既に結論がついてますけど（藁
945 ：１３２人目の素数さん：01/12/22 09:34
>>941
やっぱりインターネット文学とやらでノーベル文学賞ですか？ （藁
やっぱりインターネット文学とやらでノーベル文学賞ですか？ （藁
946 ：１３２人目の素数さん：01/12/22 09:41
「２ちゃんねる」に通信ログの任意提出要請、拒否される
http://www.asahi.com/national/update/1222/003.html
http://www.asahi.com/national/update/1222/003.html
947 ：１３２人目の素数さん：01/12/22 12:21
948 ：１３２人目の素数さん：01/12/22 13:04
>>947
山口人生大先生神帝に「地味」という言葉は無関係。
>>946 の目的は２chの管理者ひろゆき（25）が警察の
要求に屈せずログを提出しない態度をとった、よって
諸君らは安心して書き込め、っていうメッセージじゃ
ない？
山口人生大先生神帝に「地味」という言葉は無関係。
>>946 の目的は２chの管理者ひろゆき（25）が警察の
要求に屈せずログを提出しない態度をとった、よって
諸君らは安心して書き込め、っていうメッセージじゃ
ない？
949 ：１３２人目の素数さん：01/12/22 14:24
>マグレじゃないことを証明するために、ついでに、ＡＩ分野で最難問の「フレーム問題」も片付けましょうか、その内。
AI分野の最難問って記号着地問題じゃなかったっけ？
AI分野の最難問って記号着地問題じゃなかったっけ？
950 ：１３２人目の素数さん：01/12/22 14:38
>>942
「なんとなく」言われてもソースをはっきりしないと判断しようがないんですが(^^;
従来の４色問題について話をすれば･･･
４色問題＝「平面グラフの頂点彩色は４色で可能である」
と言うのは，入力大きさに依らずに彩色できる事が証明されているので，この問題は
Ｐ＝ＮＰ問題とは本質的に関係ないです．
しかし，４色問題の証明は実際の彩色を行わずに，彩色できる事を示したもので，
実際に例題が与えられた時に低いオーダーで彩色するアルゴリズムがあるのか
と言うと，これはまだ(？)だった様な気もします．
そういう意味では，実際に彩色を行う事は難しい問題なのですが，Ｐ，ＮＰ問
題というのはＹｅｓ，Ｎｏ(できる，できない)だけを問う決定問題に対しての
み定義されるので，多項式時間で実際に彩色を行うアルゴリズムができたから
と言って，即Ｐ＝ＮＰを意味する事にはならないと思います．
たぶん，頂点彩色の問題はＮＰ困難かどうか分かってないんじゃないのかなあ
･･･頂点彩色問題に詳しい人のフォロー求む．
「なんとなく」言われてもソースをはっきりしないと判断しようがないんですが(^^;
従来の４色問題について話をすれば･･･
４色問題＝「平面グラフの頂点彩色は４色で可能である」
と言うのは，入力大きさに依らずに彩色できる事が証明されているので，この問題は
Ｐ＝ＮＰ問題とは本質的に関係ないです．
しかし，４色問題の証明は実際の彩色を行わずに，彩色できる事を示したもので，
実際に例題が与えられた時に低いオーダーで彩色するアルゴリズムがあるのか
と言うと，これはまだ(？)だった様な気もします．
そういう意味では，実際に彩色を行う事は難しい問題なのですが，Ｐ，ＮＰ問
題というのはＹｅｓ，Ｎｏ(できる，できない)だけを問う決定問題に対しての
み定義されるので，多項式時間で実際に彩色を行うアルゴリズムができたから
と言って，即Ｐ＝ＮＰを意味する事にはならないと思います．
たぶん，頂点彩色の問題はＮＰ困難かどうか分かってないんじゃないのかなあ
･･･頂点彩色問題に詳しい人のフォロー求む．
951 ：950補足：01/12/22 14:47
後半ごちゃごちゃになってすいません(汗)
整理すると，
１．４色問題自体は入力の大きさに関わらず常にＹｅｓを返す事に
なるので，そもそもＰ(と言うか証明があるから定数だね・笑)
２．実際に例題が与えられた時に彩色を行いなさい，と言う頂点彩
色問題は恐らくオープン問題(クラスがまだ分かっていない)
３．もし頂点彩色問題がＮＰ困難である事が示されて，かつこれを
解くアルゴリズムが示されたらＰ＝ＮＰ．
ちなみにＮＰ困難と言うのはＮＰ完全問題から帰着できる問題のク
ラスで決定問題に限らないのですが，ＮＰ完全問題以上に難しい問
題のクラスを指して言います．
整理すると，
１．４色問題自体は入力の大きさに関わらず常にＹｅｓを返す事に
なるので，そもそもＰ(と言うか証明があるから定数だね・笑)
２．実際に例題が与えられた時に彩色を行いなさい，と言う頂点彩
色問題は恐らくオープン問題(クラスがまだ分かっていない)
３．もし頂点彩色問題がＮＰ困難である事が示されて，かつこれを
解くアルゴリズムが示されたらＰ＝ＮＰ．
ちなみにＮＰ困難と言うのはＮＰ完全問題から帰着できる問題のク
ラスで決定問題に限らないのですが，ＮＰ完全問題以上に難しい問
題のクラスを指して言います．
952 ：950さらに補足：01/12/22 14:58
３．解く→多項式時間で解く
の間違いでした(汗)
３に書いてあるように，多項式時間で解くアルゴリズムがあっても
彩色問題自体がＮＰ困難である事を示さないと意味が無いです．
の間違いでした(汗)
３に書いてあるように，多項式時間で解くアルゴリズムがあっても
彩色問題自体がＮＰ困難である事を示さないと意味が無いです．
953 ：１３２人目の素数さん：01/12/22 16:17
ねぇ、まだ次スレ立てないの？
954 ：１３２人目の素数さん：01/12/22 16:20
次スレのタイトルは何がいいだろう？
955 ：１３２人目の素数さん：01/12/22 20:58
Part 1 の時に出ていた「P=NP 証明去る」は？ >>954
956 ：１３２人目の素数さん：01/12/22 21:04
「P=NPってどうよ？」というのは…駄目か。
957 ：１３２人目の素数さん：01/12/22 21:25
もう、>>956 の「P＝NPってどうよ」ってのりでいいんでねぇの？
958 ：１３２人目の素数さん：01/12/22 21:44
P=NP 証明サルバンティンコ
959 ：１３２人目の素数さん：01/12/22 22:14
意味不明な命題にするとか
P＞NP証明去る
P＞NP証明去る
960 ：１３２人目の素数さん：01/12/22 22:19
P＝NP「人生たんと○○」
（○○には「同和の馬鹿ども」とか「腰弁の猿ども」等が入る）
っていうのは。
ドラえもん大長編のテンプレートで。
（○○には「同和の馬鹿ども」とか「腰弁の猿ども」等が入る）
っていうのは。
ドラえもん大長編のテンプレートで。
961 ：１３２人目の素数さん：01/12/22 22:23
猿でも分かるP=NP
962 ：１３２人目の素数さん：01/12/22 22:24
猿でも解けるP=NP
963 ：１３２人目の素数さん：01/12/22 22:27
神帝謹製ブーリアン扇子付き
964 ：１３２人目の素数さん：01/12/22 22:38
>963
ﾜﾗﾀ
でも、スレタイトルとしてはどうだろう（ｗ
ﾜﾗﾀ
でも、スレタイトルとしてはどうだろう（ｗ
今井の数学では、「P=NP問題」なんて、簡単ですよ。
P=NP だから NP を移項して P-NP=0.
Pでくくって、P(1-N)=0.
よって、P=0 又は N=1 でしょう。
何か？
P=NP だから NP を移項して P-NP=0.
Pでくくって、P(1-N)=0.
よって、P=0 又は N=1 でしょう。
何か？
966 ：１３２人目の素数さん：01/12/23 01:31
>>965
既出．
既出．
967 ：１３２人目の素数さん：01/12/23 03:22
じゃあ、「N=NPってどうよ？」でいいのか？立てるぞ？
968 ：１３２人目の素数さん：01/12/23 04:28
969 ：１３２人目の素数さん：01/12/23 04:50
>>961
これが好き…．
これが好き…．
970 ：１３２人目の素数さん：01/12/23 07:16
971 ：１３２人目の素数さん：01/12/23 09:33
-------------------------------------------------------------
おわりに
本スレにおいては､前スレに引き続き､神奈川大学講師の山口人生氏が自らの
ＨＰにおいて発表したＰ＝ＮＰとの証明に対して､多くの重大な問題点が指摘
された（>>850に総括）。山口氏かその偽者と推定される神帝というコテハンが
本スレに現れたものの､証明は合っているとの断定と周囲への罵倒を繰り返すの
みで､何ら有効な学術的反論を行えなかった。また､山口氏は自らのＨＰ上にお
いても有効な学術的反論を全く行なかったばかりか､ＨＰを削除して事実上証明
を取り下げてしまった。
したがって､本スレは､山口氏による証明は誤りだったと結論するものである。
今後の課題としては､山口氏の証明に対してさらに問題点を指摘するとともに､
Ｐ≠ＮＰを証明することによって本スレの結論に完全な裏付けを与えることが
挙げられる。
謝辞
本スレの執筆にあたり､重要かつ革新的なネタを提供してくださった山口人生
氏に心より感謝いたします。
----------------------------------------------------------------
おわりに
本スレにおいては､前スレに引き続き､神奈川大学講師の山口人生氏が自らの
ＨＰにおいて発表したＰ＝ＮＰとの証明に対して､多くの重大な問題点が指摘
された（>>850に総括）。山口氏かその偽者と推定される神帝というコテハンが
本スレに現れたものの､証明は合っているとの断定と周囲への罵倒を繰り返すの
みで､何ら有効な学術的反論を行えなかった。また､山口氏は自らのＨＰ上にお
いても有効な学術的反論を全く行なかったばかりか､ＨＰを削除して事実上証明
を取り下げてしまった。
したがって､本スレは､山口氏による証明は誤りだったと結論するものである。
今後の課題としては､山口氏の証明に対してさらに問題点を指摘するとともに､
Ｐ≠ＮＰを証明することによって本スレの結論に完全な裏付けを与えることが
挙げられる。
謝辞
本スレの執筆にあたり､重要かつ革新的なネタを提供してくださった山口人生
氏に心より感謝いたします。
----------------------------------------------------------------
972 ：１３２人目の素数さん：01/12/23 09:40
あとは1000ゲット競争が起きるのみ(w
973 ：１３２人目の素数さん：01/12/23 22:05
じゃ、一応1000ゲット目指してみちゃおうかな。
974 ：１３２人目の素数さん：01/12/23 22:05
よーし、パパがんばっちゃうぞー。
975 ：１３２人目の素数さん：01/12/23 22:06
って数学板じゃライバルがいないのでつまらんわ。
976 ：１３２人目の素数さん：01/12/23 22:42
それはどうかな？
977 ：１３２人目の素数さん：01/12/24 01:44
じゃぁ3日くらいかけてﾏﾀｰﾘ1000狙うか。(w
978 ：１３２人目の素数さん：01/12/24 22:06
978
979 ：１３２人目の素数さん：01/12/24 22:44
９７９＝N９７９
980 ：１３２人目の素数さん：01/12/24 23:19
π＝νπ
さるげっちゅ