P=NP問題について真面目に語るスレ

1 ：厨輪：03/07/23 13:02

真面目に議論しましょう。

2 ：厨輪：03/07/23 13:03

・・・というのは、P=NPでgoogleってみてもわかるように
元＊＊＊大学の＊＊＊＊とかいう人が、NPの定義も
Cookの還元も、ろくに知らないで、P=NP問題を解決した
とかなんとかわめき散らしていて、また、P=NPもロクに
知らない連中が、ただオカシイ人がいるというだけで、
一昨年以来、P=NPよりもこの人を話題にしたスレッドを
だらだらとしまりもなくつづけていて、いい加減吐き気を
催してきたからです。

そろそろ真面目にP=NP問題について
語ってもいいんじゃないのか？

3 ：_：03/07/23 13:07

http://homepage.mac.com/hiroyuki44/

4 ：厨輪：03/07/23 13:07

まず用語の定義から

クラスPとはDTM（決定的チューリングマシン）によって、
多項式時間で解けるすべての探索問題のクラス
クラスNPとはNDTP(非決定的チューリングマシン）によって、
多項式時間で解けるすべての探索問題のクラス

P=NP問題は、この二つのクラスが一致するかどうかを問う

5 ：supermathmania ◆ViEu89Okng ：03/07/23 13:09

わりと有名な話からいってみよう。
フィボナッチ数列の計算アルゴリズム
a=0,b=1とする。c=b,b=a+c,a=cを必要な回数繰り返してbを求めるのと、
f(n)=f(n-1)+f(n-2),f(1)=1,f(0)=0によって再帰的に計算するのでは、
再帰計算の方がずっと時間がかかる。(計算時間が指数増大する。)
前者は、計算時間は1次オーダーで増大する。

6 ：１３２人目の素数さん：03/07/23 13:09

http://www.e-mansion.co.jp/kensyou/

7 ：厨輪：03/07/23 13:18

問題XがNP困難(NP-hard)とは、任意のNPに属する問題が
多項式時間でXに還元できることを指す。
このXがクラスNPに属する場合、XをNP完全(NP-complete)という。

8 ：１３２人目の素数さん：03/07/23 13:27

NP問題の特徴

解が与えられれば、それが正解であるか否かは
すぐに(多項式時間で)判別できる。

9 ：１３２人目の素数さん：03/07/23 14:02

>>4
探索問題を定義してくれ．決定問題のことかな．
本来 P や NP は決定問題に限らないよ．
>>8
それだとすべての決定問題が NP になっちゃうので正しくない．

山口元先生のスレには詳しい人も多いので勉強になるよ．

10 ：１３２人目の素数さん：03/07/23 14:10

>>9
＞探索問題を定義してくれ．決定問題のことかな．

丸善のコンピュータ基礎理論ハンドブックⅠに
書いてあるので読んでくれるかな。

山口スレの専門家はこちらに移動したよ。

11 ：厨輪：03/07/23 14:19

詳細については、早稲田大学の守屋悦朗氏による
以下のページを参照ください。

計算の複雑さとは何か
www.em.edu.waseda.ac.jp/~moriya/research/complexity.html

例えば>>8さんのいわんとするところは以下の定理でしょう。
定理５　L∈NP であることと，次のような多項式時間アルゴリズム A が存在することとは同値である：
　任意の x に対して，x の長さの多項式程度の長さの y をうまく選べば x∈L かどうかを A によって（x の長さの多項式時間で）判定できる．

12 ：１３２人目の素数さん：03/07/23 14:28

”解”と書くと>>9のような知ったかでもつっこめてしまう。
でも>>9は正しい内容が何かフォローできない。

山口スレの勉強ってそんなもんだよね（プ

13 ：１３２人目の素数さん：03/07/23 16:06

マジで日本で一番P=NPに近い人って誰？

やっぱ日大の戸田誠之助？

14 ：１３２人目の素数さん：03/07/23 18:39

理系板の情報科学総合スレッドとかで真面目な話ができると思うよ>>1
いまんとこラムダ計算とかプロセス代数なんかの話題が中心だけど

数学板だと…基礎論スレがベストなんだろうけど、なんせ"NP"の名前を出しただけで
夏厨が流入してくるような状況だしなあ＞数学板

15 ：１３２人目の素数さん：03/07/23 19:38

夏厨ならば秋にはいなくなる訳だが

16 ：１３２人目の素数さん：03/07/23 20:24

>>15
半年で議論に片をつければいいわけだな。

17 ：厨輪：03/07/24 11:29

今日も用語の定義から

P,NPに関する、>>4とは別の定義

言語LがクラスPに属するとは、多項式時間限定の
DTMにて受理可能であることを指す
言語LがクラスNPに属するとは、多項式時間限定の
NDTMにて受理可能であることを指す

クラスco-NPとは、クラスNPに属する言語の補集合

18 ：厨輪：03/07/24 11:35

例えば、ﾌﾞｰﾙ式の充足判定はNP、ﾄｰﾄﾛｼﾞｰ判定はco-NPに属する。

前者がNPに属することの証明

適当なﾌﾞｰﾙ値の割り当てに対して
充足性を判定する時間が
多項式時間内であることを
示せばよい。
（つまり、命題がﾄｰﾄﾛｼﾞｰであった場合に
　それが多項式時間でわかる必要はない！）

19 ：厨輪：03/07/24 11:40

>>18
＞つまり、命題がﾄｰﾄﾛｼﾞｰであった場合に
＞それが多項式時間でわかる必要はない！

しかし、充足可能な場合にその判定が
多項式時間で出来るならば、その結果
充足不能な場合の判断も多項式時間で
できる、とはいえる。

20 ：１３２人目の素数さん：03/07/24 12:03

>>12
＞理系板の情報科学総合スレッドとかで真面目な話ができると思うよ
確かにふざけてないけど、真面目というには中身が薄いな。

ところで、計算量理論は基礎論とは違うよ。
別に夏厨とは無関係。てか夏厨退治できないのは
書き手がそろいもそろってローレベルだから。

21 ：１３２人目の素数さん：03/07/24 14:10

>>19

P=NPならば、NP=co-NP　(すなわちP=co-CP)
実際は
P=co-NPのとき、そのときに限りP=NP
もいえる。
（ただしNP=co-NPからP=NPはいえない）

22 ：１３２人目の素数さん：03/07/24 14:45

>>21
「NP=co-NPからP=NPはいえない」とはいえていないんじゃないでしょうか？
本当に「いえない」といえるということは not P=NP がいえることですから。

23 ：22：03/07/24 14:49

訂正：
本当に「いえない」といえるということは P=NP が証明できないと
いうことを意味するから。 ,,,でした。

24 ：１３２人目の素数さん：03/07/24 15:32

>>22

NP=co-NPでも、P=NPの場合もあるしnot P=NPの場合もある
だから「いえない」。これが正しい日本語。君は間違ってる

25 ：１３２人目の素数さん：03/07/24 15:56

>>24
よく意味がわからないのですが P=NP というのは相対化
されているものをいっているのですか?
つまり、パラメーターがあるものなのでしょうか?
それなら別ですが、そうでなく P=NP 問題といわれている
ものなら24の表現をするのはヤマジンだけだよ。

26 ：１３２人目の素数さん：03/07/24 16:40

>>20
おっ、基礎論スレの人だ！
なんか書いて書いてー

27 ：１３２人目の素数さん：03/07/24 16:43

>>25
オラクルは関係ないよね。
もしかして君はNP=co-NPならばP=NPだといってるの？
そうなら、そういってるのは君だけだよ。

28 ：１３２人目の素数さん：03/07/24 20:44

>>27
よろしいですか?
「X から Y がいえない」ということが証明できるというのは
たとえば X が成立していてなおかつ Y が不成立なモデルを
つくることです。一般に「いえない」ということは、「私はいえない」
ということは易しいのですが、数学の命題として「いえない」という
ことは否定命題が証明できる場合を除き、証明することは難しいもの
です。
24 の「NP=co-NPでも、P=NPの場合もあるしnot P=NPの場合もある」
というのは、とても粗雑な非論理的な表現で数学のわかる人は
しない表現です。

29 ：１３２人目の素数さん：03/07/24 21:05

要するに今のところNP=co-NPからP=NPが導かれることも、
またNP=co-NPからP≠NPが導かれることも証明されていないと
>>21は言いたいのだろう。

30 ：１３２人目の素数さん：03/07/24 21:18

>>28　考えすぎ。
>>29　あんたが正しい。

31 ：１３２人目の素数さん：03/07/25 01:49

多項式クラスと非多項式クラスという以外にも階層に関する議論はあるのですか？
指数関数クラス以外に、それよりももっと計算量の多いクラスとか。
たとえば指数関数を指数に持つ関数とか、指数関数を指数関数回適用した
関数とか、、、、、

32 ：厨輪：03/07/25 10:59

>>31
上を見ればキリがありませんよ（ｗ

多項式時間のクラスPと指数関数時間のクラスEXPの間に注目した場合
興味深いクラスとして、NP、co-NPのほかに、PSPACEがあります。
これは多項式領域限定のDTMで受理可能な言語全体のクラスです。
(この場合NDTMにしても、同じになることが知られています）
PSPACEは、NP及びco-NPを含みますが、これ自身Pと同じかどうか
まだ知られていません。又EXPと同じかどうかも知られてません。

今のところ明らかなのはPとEXPは等しくないということくらいです（ｗ

33 ：３３：03/07/25 11:46

34 ：私を受理してください：03/07/25 23:42

┏━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┓
┃Ｂ┃１┃０┃１┃１┃０┃０┃０┃１┃１┃１┃１┃０┃１┃０┃１┃Ｂ┃
┗━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┛
　　　　　　　↑
　　　　　　┏━┓
　　　　　　┃Ｐ┃
　　　　　　┗━┛

35 ：私を受理してください：03/07/26 00:09

┏━┳━┳━┳━┳━┳━┓
┃Ｂ ┃山┃口┃人┃生┃Ｂ┃
┗━┻━┻━┻━┻━┻━┛
　　　　　　　↑
　　　　　　┏━━━┓
　　　　　　┃P=NP　┃
　　　　　　┗━━━┛

36 ：１３２人目の素数さん：03/07/26 01:24

チューリングマシンで、テープが一次元になっていますが、
テープが二次元的に記録が出来ても、そのような二次元チューリング
マシンにできることは一次元のものと同じなのでしょうか？

37 ：１３２人目の素数さん：03/07/26 01:30

面目を保つにはどうしたらよろしいのでしょうか？

38 ：１３２人目の素数さん：03/07/26 06:07

NP完全性は学部で習うけど、現時点でP≠NPに取り組んでる人は日本にいないと思う。
そもそも日本の計算量プロパーってせいぜい10人くらいなんでは？

39 ：１３２人目の素数さん：03/07/26 09:31

＞そもそも日本の計算量プロパーってせいぜい10人くらいなんでは？

その方々の名前を具体的に挙げていただけませんか？
渡辺治さんは知ってますけど、他にどんな人がいますか？

40 ：１３２人目の素数さん：03/07/26 15:17

西野哲朗氏とか戸田誠之助氏とか

41 ：１３２人目の素数さん：03/07/26 15:29

>>40

それで三人だね。あと七人！

42 ：１３２人目の素数さん：03/07/26 15:45

１０人もいないだろうよ

43 ：１３２人目の素数さん：03/07/26 15:48

竹内外史さんも退官後はP=NP問題を一人でｼｺｼｺ考えてるって書いてたな

44 ：１３２人目の素数さん：03/07/26 20:46

>>42
でも三人ってことはないんじゃない？
だったらせいぜい五人っていうはずだもの。
少なくとも五人は名前を挙げられるんじゃない？

45 ：ぼるじょあ ◆yBEncckFOU ：03/08/02 03:23

　　　　∧＿∧　 ∧＿∧
ﾋﾟｭ.ｰ　（　・３・） (　　＾＾）＜これからも僕たちを応援して下さいね（＾＾）。
　　＝〔~∪￣￣￣∪￣￣〕
　　＝ ◎――――――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉&ぼるじょあ

46 ：１３２人目の素数さん：03/08/04 17:57

>>38
日本でもいるよ．
例えば京大の岩間先生とか回路計算量の下限の証明に取り組んでいる．

47 ：１３２人目の素数さん：03/08/19 07:02

48 ：１３２人目の素数さん：03/08/19 08:06

予想としてはＰ=/=ＮＰなので
Ｐ=/=ＮＰ問題では？

49 ：１３２人目の素数さん：03/08/19 08:12

>>48

「きごう」で変換＞≠

50 ：１３２人目の素数さん：03/08/19 09:16

>>48
肯定か否定かわからない問題の場合、予想がどちらであっても
肯定命題を問題とするのは別におかしいとは思わないけどね。

51 ：１３２人目の素数さん：03/08/19 23:50

盛り上がりませんナ。
こちらにもヤマジン大先生にお越し願わなくては。

52 ：１３２人目の素数さん：03/08/20 12:03

>>51
確かに、ヤマジン自身は大真面目だからな。ただ、ヤマジンが
書き込んだことに真面目に反応するのは遠慮したいね。

53 ：神帝：03/08/26 01:02

猿ども、抵抗はそれまでか？

54 ：１３２人目の素数さん：03/09/12 16:15

人生ﾀﾝのｽｯﾄﾞﾚが消滅。今後どうなるのか？

55 ：１３２人目の素数さん：03/09/12 21:57

>>54
つづいてるよ。

56 ：１３２人目の素数さん：03/09/23 18:52

山口人生様、ついに自己の証明の根幹部が誤りであったと認めました。

どうやらクレイ研に特攻をかけ、玉砕したためにこれまでの論文を
破棄せねばならなくなった模様。

57 ：１３２人目の素数さん：03/10/04 23:59

この手の難問を解くブレークスルーは、狭い定義に固執せずに、ちょっと広げた（一見するともっと難しい）問題に対してアプローチすることだと思います。
この分野の日本の理論家は優秀ですが、自由な発想という意味では弱いですね。

58 ：１３２人目の素数さん：03/10/05 00:23

竹内外史さん以外の日本のP=NP研究者を2人ほど、みつけました。
ほかにも何人かおられるでしょう。

やはり、数学基礎論からのアプローチが正解なのでしょうか？

http://www2.math.human.nagoya-u.ac.jp/Staff/yasumoto.html
http://wwwmi.cias.osakafu-u.ac.jp/~suzuki/index-j.html

59 ：１３２人目の素数さん：03/10/10 21:56

http://eprint.iacr.org/2003/187/

こういうのはどうでしょうか．自分ではとても正しさを検証できないですが，
もしそうだとすると，これは鬼のような結果．

ちなみに，著者は一流の complexity 研究者と言って良いと思う．

60 ：権能：03/10/11 23:42

オイオイ、糞塵アホ猿が戯言ほざいているぜ。
まだ恥をかきたいのか？
山口人生様が「Ｐ＝ＮＰ？」問題を解いた。
何か文句あるか？
素人は、黙ってろ。

61 ：１３２人目の素数さん：03/10/15 20:04

神奈川大が数学で公募してるな（笑）

62 ：１３２人目の素数さん：03/10/17 22:09

岩間さんの教科書、なかなかよさげ

63 ：１３２人目の素数さん：03/10/18 20:26

class of P / class of NP |∽| N / R

N ≠ R

∴ P ≠ NP (EOT)

64 ：１３２人目の素数さん：03/10/28 19:28

どなたか、山口人生様の行方をご存じないでしょうか？
23日の第２回公判からこっち、とんとお見かけしないのですが・・・。

65 ：１３２人目の素数さん：03/11/10 07:31

66 ：１３２人目の素数さん：03/12/03 17:55

67 ：１３２人目の素数さん：03/12/03 18:08

68 ：１３２人目の素数さん：03/12/09 23:57

敗訴age

69 ：１３２人目の素数さん：03/12/12 23:39

新課程の高校の数Aに有りそうな問題(ｾﾝﾀｰでは選択問題に移行)

3人から2人を選んでｾｸｰｽする順列は?
3P2(←P:Play)

3人から2人を選んでｾｸｰｽする組合せは?
3C2(←C:ｾｸｰｽ)

"P"の場合は同一人物同士のｾｸｰｽにおいて､上と下の立場が逆転する場合も考慮する

70 ：１３２人目の素数さん：03/12/14 18:14

>>69
P=NP に何にも関係ないし
おまけにそれ算数だし

71 ：１３２人目の素数さん：03/12/17 11:21

　　　　|　　　　　　　　　　　　　|
　　　　|　　　　　　　　　　　　　|
　　　　|　　　　　　　　　　　　　|
＿＿ノ　　　　　　　　　　　　　 |　　　＿
| |　　　　　　　　　　　　　 |　　ノ＼__ヽ　　
ヽ二二ヽ -―- ､　　　　　　 | 　＼ノ（◎）
＿____／　／"￣ヽヽ＿＿＿＿|
　　 /　 /　_∧＿∧ l　OKOK。問題無い。
　　 |　 |／（　´_ゝ｀） |　　　　　　＼
　　ヽi⌒￣＿/￣￣￣￣/ﾟ｡　　　　＼
　　　＼　＼./　 FMV　 / ＼.　　　　　＼
　　　＼ソ/＿＿＿＿/ ＼ノ
　　　　　　＼＼::::::::::::::::: ＼＼
　　　　　　　＼＼_::::::::::::＿））
　　　　　　　　ヽ-二二-ン

72 ：１３２人目の素数さん：03/12/24 21:30

ハングル板の「韓国マスコミ今日のホームラン！！74」
http://ex.2ch.net/test/read.cgi/korea/1071971027/l50
の293によると、全北大金ヤンゴン教授らのグループがP=NP問題を証明したと
発表したようです。

http://korea.hanmir.com/ktj.cgi?url=http://kr.news.yahoo.com/service/news/ShellView.htm%3fArticleID%3d2003122415404542701%26LinkID%3d61%26News

73 ：１３２人目の素数さん：03/12/24 22:02

>>72
素因数分解が P であったって、P=NP ではないだろう？

74 ：あげ：03/12/26 18:36

今、人生タンのＨＰ見ようとしたら、消えていたんだけど、
どうなったのか知っている人いる？
裁判の結果は？

75 ：１３２人目の素数さん：03/12/28 21:59

たまにはP≠NPの方向で証明するトンデモも見てみたいな。

76 ：１３２人目の素数さん：03/12/30 16:01

>>74
裁判にかまけててドメイン更新忘れて旧ドメイン名がDNSから消え去った。

新ドメイン
http://www.boolean-game.com/news1.htm

なお、彼に関しては個人スレ参照のこと。
ﾔﾏｼﾞﾝ14
http://science2.2ch.net/test/read.cgi/math/1065701918/

>>75
人生は2ch登場時点でP=NPと言っていたが、「その証明は間違っている」
と言われ即刻結論のみP≠NPと書き換えて現在に至る。

77 ：通りすがり：03/12/30 17:40

>76

どうもありがとう～
個人スレもあったんですね。
でもヤマジンじゃわかりませんね・・・。

78 ：甲陽高１ ◆uqmQ5k/uJs ：03/12/30 17:53

>>1
P=NPって何それ？　
両辺Ｐで割ってＮ＝１だろ？　
お前ら・・どんだけ頭糞なんだよ・・・

79 ：１３２人目の素数さん：03/12/30 17:58

P≠NPならアフォにも天才に勝てるチャンスがありまつね

80 ：１３２人目の素数さん：03/12/30 19:09

>>78　いいね。

R∈R ＝￢R∈Rって何それ？
両辺R∈Rで割って￢＝1だろ？
お前ら･･どんだけ頭糞なんだよ･･･

81 ：オーバーテクナナシー：03/12/30 20:42

>>72
マジ?。
実際にP=NPって証明されると、なんか夢が一つ無くなったような気分。

82 ：１３２人目の素数さん：04/01/03 20:52

んなバカな。
P=NP だったら、計算量理論のここ数十年の理論が全部水泡に帰するよ。

83 ：１３２人目の素数さん：04/01/03 21:29

>>82
間違い無いニダ

84 ：１３２人目の素数さん：04/01/04 11:44

万能チューリングマシンよりも強力な計算機の上でも NP≠P が示せれば，
万能チューリングマシンと等価な計算機の上では NP≠P が云える．
そのより強力な計算機の上で万能チューリングマシンをインタープリット
出来さえすればよいからだ．

それでは，具体的にはどのような計算機を持ってくればよいだろうか?
はたしてそれが量子計算機なのだろうか?

85 ：１３２人目の素数さん：04/01/08 23:31

オイ、７６のキチガイ餓鬼
内容も理解できずに、戯言こくな。
パラドックスって知ってるか？
山口人生様が「Ｐ＝ＮＰ？」問題を解いた。

86 ：１３２人目の素数さん：04/01/08 23:36

山口人生様の１５番目のスレは何処だ？

87 ：↑：04/01/09 02:08

ここだ↓（ｗ
http://science2.2ch.net/test/read.cgi/math/1072966661/

88 ：１３２人目の素数さん：04/01/10 16:08

山口人生様の結果を無視して、「Ｐ＝ＮＰ？」問題が真面目に語れるはずもない。
ここの書き込みは、全て、戯言。

89 ：１３２人目の素数さん：04/01/10 23:36

山口人生ﾀﾝの結果を無視せずして「Ｐ＝ＮＰ？」問題が真面目に語れる筈はない。

90 ：１３２人目の素数さん：04/01/16 03:38

「Ｐ＝ＮＰ？」問題を解いたつもりになり切ってしまっているオメデタイ山口人生様（ｐ；

91 ：１３２人目の素数さん：04/01/18 00:37

もしや、既存の体系の中では証明不能な命題なのではないか?
それなら公理にとることも可能だな。

92 ：１３２人目の素数さん：04/01/18 00:58

>>91
それは不自然じゃない？充足可能性問題の計算量が
￢NP=Pの公理系とNP=Pの公理系によって変わってしまうことになるのかな？

93 ：疑問：04/01/19 15:18

Pである問題というものは、多項式時間による解法が示された問題だ。
NPである問題というものは、答えが分かったと主張するものが居たときに
それの検証が多項式時間で可能だということが示された問題だ。

NPの問題の入力サイズMが与えられたときに、次のような問題が
あれば、どうなるか。入力サイズMに対してMの多項式時間の解法は
確かに存在するのだが、その解法を生成することがアルゴリズム的に
不可能であるか、もしくは解法の生成自体にMの多項式では押えられない
計算量が掛かる、という可能性だ。

また、通常のPの問題とそれに対する解法というものを考えてみると、
解法自体は有限長の記述でなされている。もしも空想するに、NPに
たいして多項式時間による解法があったとしてその記述自体、あるいは
記述を発見することに多項式では押えられない計算量がかかると
したらどういうことになるのだろうか?

94 ：１３２人目の素数さん：04/01/19 16:48

>>93
以下の語の定義を述べよ。話はそれからだ。

・P
・NP
・チューリングマシン

95 ：１３２人目の素数さん：04/01/19 22:16

一般に2-tape deterministic Turing machineの動きを
1-tape deterministic Turing machineでシミュレートするには
どうすればいいのですか？

96 ：１３２人目の素数さん：04/01/20 21:48

>>93
＞入力サイズMに対してMの多項式時間の解法は確かに存在するのだが

生成せずに存在は示されない。（終）

97 ：１３２人目の素数さん：04/01/21 00:57

排中律を仮定すれば、ある命題は真であるか偽であるかのいずれかである。
でも任意の命題を証明する一般的な有限停止のアルゴリズム(有限長の
プログラムで、入力が与えられる以前に固定されたもの)は無い。
但し、このことは長さに限度のないプログラムや、入力が与えられたら
それに応じてプログラム自身を変化させるような場合を除外
しきれていないように思うのだが、如何だろうか?

同様に、例え仮に多項式時間の解法が存在しているかもしれなくても、
それを示すことが一般的には出来ない、というような機構があれば、
NP＝Pか、という問題は決定不能になる。

98 ：１３２人目の素数さん：04/01/21 03:36

>>97

> このことは長さに限度のないプログラムや

長さに限度がなければ、有限時間で終わりません。

> 入力が与えられたら
> それに応じてプログラム自身を変化させるような場合

どのように変化するかを記述できれば、
それは上述のアルゴリズムの範疇です。

99 ：１３２人目の素数さん：04/01/21 08:05

>>97
P=NPが決定不能になるのは、多項式時間の解法が
「存在していない」場合に限られる。
存在する場合には、それを示せばよい。
しかし存在しない場合に、その証明（証明は
アルゴリズム同様、長さに限度がある。これ
は常識）があるとは限らない。

100 ：１３２人目の素数さん：04/01/21 08:09

＞存在しているかもしれなくて

「存在していない」が、それが証明できない場合
「非標準解法」があるという公理を付け加えても
矛盾を導くことができない。しかし、これは
解法が存在する、ということではなく、単に
形式的自然数論の不完全性によるものである。

101 ：１３２人目の素数さん：04/01/21 22:47

>>99

（NP完全問題の）多項式時間の解法が存在しないことが
証明されれば、P≠NP が証明されるよね。
決定不能にはならないよ。

102 ：１３２人目の素数さん：04/01/22 03:01

後の可能性は、「数学的には証明が可能であり得る」が、「現実的には
証明が不可能」である場合だ。
例えば、証明を行うのに必要な「最小の記述」中に現れる記号の数が、
10＾10＾10 以上ある、なんていう状況だと、宇宙の原子1個に一つの
文字を記号として描き込めても、書きつくせない。
仮に、囲碁が先手必勝であることが真だとしてみよう、するとその
証明があるはずだが、もしもそれを書くのに必要なページ数が
10＾1000になったりすれば、現実的には証明は無いのと同じだ。

103 ：１３２人目の素数さん：04/01/22 11:06

>後の可能性は

何の可能性？P vs NP とは関係の無い話のようだけど。

104 ：１３２人目の素数さん：04/01/22 16:43

>72
>ハングル板の「韓国マスコミ今日のホームラン！！74」
>http://ex.2ch.net/test/read.cgi/korea/1071971027/l50
>の293によると、全北大金ヤンゴン教授らのグループがP=NP問題を証明したと
>発表したようです。
>http://korea.hanmir.com/ktj.cgi?url=http://kr.news.yahoo.com/service/news/ShellView.htm%3fArticleID%3d2003122415404542701%26LinkID%3d61%26News

関連情報
http://mathforum.org/epigone/sci.math.research/slerdcomflar/malwk9zq6mkr@legacy
http://math.uww.edu/~namk/resume.pdf

Ki-Bong.Nam,.S..H..Wang.and.Y..G..Kim:.Linear.Algebra,.Lie.Algebra.and.their.applications.to.P.versus.NP.
Presentations.at.National/International.Conferences:

Lie代数って何？

105 ：１３２人目の素数さん：04/01/22 17:14

>104

http://ipam.chonbuk.ac.kr/default1.htm
にPvsNPの論文がPDF等でおいてあるよ．

106 ：１３２人目の素数さん：04/01/23 03:24

>103
P=NPの証明あるいはP!=NP
の証明が数学的にはあったとしても,その記述が物理的に不可能あるいは
現実的に不可能であれば,発見すらできないはずだ.

107 ：１３２人目の素数さん：04/01/25 19:29

>>99
それは強すぎるな。

「P=NP が証明できれば、その証明は構成的である」のであればそうだが、
たとえ P=NP でもアルゴリズムを構成できない場合だってある。
あるアルゴリズム A が NP完全問題を解けるものかどうかを
決定することが不可能な場合とか。

108 ：１３２人目の素数さん：04/01/27 19:01

ある問題がPであるかどうかを一般的に判定するアルゴリズムは存在しない。
ある問題がNPであるかどうかを一般的に判定するアルゴリズムも存在しない。

ある問題がNPであることが分かっているときに、それがPであるかどうかを
判定するアルゴリズムも一般にはないことが言えないのだろうか?

109 ：１３２人目の素数さん：04/01/28 01:10

線形計画法はLPだが、NPであることはすぐに分かる。
ところが、最近になってLPには多項式時間の解法があることが
わかった。つまりLPというNPの問題がPで解けることが示されたのだ。

110 ：１３２人目の素数さん：04/01/28 01:18

>>109
バカバカしすぎてﾜﾛﾀ…＿|￣|○

111 ：１３２人目の素数さん：04/01/28 01:33

それが大事

112 ：１３２人目の素数さん：04/01/28 01:51

>>109
釣りですか('A`)

113 ：１３２人目の素数さん：04/01/28 02:01

素数判定は単純に考えて NP であることはすぐに分かる。
ところが、最近になって素数判定は多項式時間で行えることが分かった。
つまり、インド人もびっくりということだ。

114 ：１３２人目の素数さん：04/01/30 17:33

``代数幾何方面からP vs NPを解決しようとしてる人がいるらしい''
て聞いたことがあるんですけど
一体どんなアプローチなんですかね
詳しい人，教えて！

115 ：１３２人目の素数さん：04/01/31 06:51

どこが馬鹿馬鹿しいのかな? 正しいこと書いてるみたいじゃん。

116 ：詳しくない人：04/01/31 10:17

>>114
この方かしら
http://www.vldb.org/dblp/db/indices/a-tree/m/Mulmuley:Ketan.html

117 ：１３２人目の素数さん：04/02/03 22:44

>>116
どもありがとう

118 ：恒勝：04/02/23 14:58

フフン
猿

119 ：恒勝：04/02/23 17:34

今年に入って、山口人生様の追っかけか。
真似猿。
見よ、この醜さを。
自分達が先に議論していたかのような証拠を残そうと画策している。
裏情報の盗作馬鹿。

120 ：１３２人目の素数さん：04/02/23 18:16

＞今年に入って、山口人生様の追っかけか。

うむ。P VS NP系のトンデモと言う意味では
完全にﾔﾏｼﾞﾝの追っかけだな。

121 ：恒勝：04/02/25 08:56

１２０のキチガイ餓鬼よ
フフン。
また歴史上、証拠が残ったぞ。
間抜けが。
この時点（２００４年２月２５日）で、山口人生様が「Ｐ＝ＮＰ？」問題を完全解決したと認知できてないわけだ、日本猿には。

122 ：１３２人目の素数さん：04/02/25 18:13

＞この時点（２００４年２月２５日）で、山口人生様が「Ｐ＝ＮＰ？」問題を完全解決したと認知できてないわけだ、日本猿には。

外国には認知した奴がいるとでも言うのだろうかｗ

123 ：１３２人目の素数さん：04/02/26 00:34

チュ-リングマシンの停止問題は、あるマシンAが停止することの証明が
見せられれば、それを確認するのはPだろうと思うので、たぶんNP問題だが、
一般的にはチュ-リングマシンの停止性はそのプログラムをみても
アルゴリズム的には決定不能である、つまりPではない。
だからPとNPは等しくないと思うよ。

124 ：１３２人目の素数さん：04/02/26 03:31

電波ｷﾀ─ｗｗﾍ√ﾚｖｖ～(ﾟ∀ﾟ)─ｗｗﾍ√ﾚｖｖ～─ !!

125 ：１３２人目の素数さん：04/03/07 02:04

331

126 ：１３２人目の素数さん：04/04/01 08:13

874

127 ：１３２人目の素数さん：04/04/10 01:52

最近、この問題の進展がさっぱりないな。

128 ：１３２人目の素数さん：04/04/12 09:38

数論からの独立性って、なんのことなの

129 ：１３２人目の素数さん：04/04/26 03:30

705

130 ：１３２人目の素数さん：04/05/05 23:22

853

131 ：１３２人目の素数さん：04/05/20 16:23

748 名前：１３２人目の素数さん[sage] 投稿日：04/05/20 01:47
ついに完結か

ところで結局巡回問題は多項式時間で解けるの？解けないの？

757 名前：１３２人目の素数さん[] 投稿日：04/05/20 14:15
７４８のキチガイ餓鬼よ
何の関係があるんだ、「Ｐ＝ＮＰ？」問題と？

こんな馬鹿がチャレンジしてると思うと・・・。

132 ：１３２人目の素数さん：04/05/20 16:24

あ、↑は山口人生ね。

133 ：１３２人目の素数さん：04/05/24 01:12

104に書いてある
>ハングル板の「韓国マスコミ今日のホームラン！！74」
>http://ex.2ch.net/test/read.cgi/korea/1071971027/l50
>の293によると、全北大金ヤンゴン教授らのグループがP=NP問題を証明したと
>発表したようです。
ってその後どうなったの？

134 ：１３２人目の素数さん：04/05/29 21:02

age

135 ：１３２人目の素数さん：04/06/06 08:07

933

136 ：１３２人目の素数さん：04/06/06 23:23

せっかく更新したのにﾔﾏｼﾞﾝｽﾚはもうない・・・
モロ2chを意識した内容だったのに、これでは実に
無意味ですね。

137 ：１３２人目の素数さん：04/06/07 07:02

あるよ。

【ﾘｼﾞｪｸﾄ】ヤマジンの情報脳内大戦17【上等】
http://science3.2ch.net/test/read.cgi/math/1086333865/

138 ：１３２人目の素数さん：04/06/07 08:02

>>137
136ですｻﾝｸｽｺ。
毎回スレタイがいろいろ変わる難しいインターネットです。

139 ：１３２人目の素数さん：04/06/14 07:00

407

140 ：１３２人目の素数さん：04/06/22 09:31

307

141 ：１３２人目の素数さん：04/07/01 18:37

877

142 ：１３２人目の素数さん：04/07/07 01:52

決定不能なのかも知れないなぁ。

143 ：１３２人目の素数さん：04/07/22 02:12

何かうまいモデルのようなものが作れないかな。
それで、モデルとしてN＝NPのものと、N≠NPの両方が作れれば、
面白いことになるんだけど。

144 ：１３２人目の素数さん：04/07/27 21:05

どう面白いのか

145 ：１３２人目の素数さん：04/08/06 22:07

312

146 ：１３２人目の素数さん：04/08/13 16:30

266

147 ：１３２人目の素数さん：04/08/21 02:29

866

148 ：１３２人目の素数さん：04/08/21 02:39

>>144
とりあえず、教科書のページが増える。

149 ：１３２人目の素数さん：04/08/27 23:23

437

150 ：１３２人目の素数さん：04/09/04 15:20

268

151 ：１３２人目の素数さん：04/09/05 00:40

素因数分解がPでないことが示せれば、P≠NPが言えるのだろうかな?

152 ：１３２人目の素数さん：04/09/05 00:49

>>151
素因数分解はNP完全じゃないからそれは違う。
そもそも素因数分解はPに入ることが証明されたはず。

153 ：１３２人目の素数さん：04/09/05 02:07

>>152
＞そもそも素因数分解はPに入ることが証明されたはず。

素数判定じゃなくて？

154 ：１３２人目の素数さん：04/09/05 02:16

>>153
あ、そうかも。勘違いスマソ。

155 ：１３２人目の素数さん：04/09/06 14:43

素因数分解 in NP なので，素因数分解 not in P ならば
NPに入るけどPに入らない問題があるからNP≠Pが言える．

156 ：１３２人目の素数さん：04/09/06 15:18

「NP完全な問題が1つでもPに入る事が示されればP=NP」ってのと
ごっちゃになってるな。

157 ：１３２人目の素数さん：04/09/06 15:50

>>155
> 素因数分解 in NP なので，素因数分解 not in P ならば
あのー、P\subseteq NP なんですけど。

158 ：１３２人目の素数さん：04/09/06 15:52

>>157
だから何。

159 ：１３２人目の素数さん：04/09/09 16:05

>>157は何が言いたいの。
教えてエ◇イ人。

160 ：１３２人目の素数さん：04/09/09 18:34

>>158 >>159
155 は間違いということでしょ．

161 ：１３２人目の素数さん：04/09/10 01:17

>>160
157が間違ってるわけだが。

162 ：160：04/09/10 03:24

>>161
額面どおり答えてしまった．
罪滅ぼしにまとめると，
151 の答えは Yes
152 は素因数分解が NP 「完全」かどうかは 151 には関係ないから間違い．
155 は 151 への返答として妥当．
156 は 152 への意見でこれも妥当．
157 は 155 の主張に関係ない
ですね．

163 ：１３２人目の素数さん：04/09/10 22:35:16

>>162
だね。157は言っている内容自体は間違っちゃいないわな。
何を主張しようとしているかを考えれば、勘違いをしているのは
確かだけど。

164 ：１３２人目の素数さん：04/09/12 20:04:10

これが答だよと言われてそれが本当かどうかを検証する手間がPな問題をNP
という。NP問題のどれでもいいからPではないことを示せればP＝NPは否定される。

逆に、もしもP＝NPを示そうと思うならば、NP完全といわれる問題のどれでもいいから
その一つがPであることを示せばよい。

165 ：１３２人目の素数さん：04/09/13 00:57:27

　　::::::::::::::::::::　　　　　　　　ｸｿｽﾚ神　　　　　　　　　　 ::::::::::／）:::::::::
:::::（＼:::::::　　　　　　　　　　　　↓　 _人　　　　　　　　　／　／　):::::::::::
:::::/＼＼　　　　　　　　　　　　　ノ⌒　丿　　　　　　　／　／　／ヽ::::::::::::
:::: ヽ　＼＼　　　　　　　　＿／　　 ::（　　　　　　　／　／　／　／::::::::::::::::
:::: （＼　＼＼　　　　　　/　　　　　:::::::＼　　　　　ｌ　三　／　／　）:::::::::::::::
:::::::ヽ　ヽ . ミヽヽ　　　　（　　　　　:::::::;;;;;;;）　　　/　　　二　／　／::::::::::::::::::
::::::: ( ＼　ヽミヽヽ　　　＼＿――￣￣::::::::::　 /　　　　二 ___／ヽ　...::::::::::::::
::::...　/ヽヽ　ﾆ　ヽヽ　　ﾉ￣　　　　　:::::::::::::: ／／　　ニ _______／　　　...:::::::::
:::.　　ヽ____　　ﾆ　ヽ　（　´Д｀　 ::::::::::::::;;;;／／　　　ニ ____ノ　　　　　.....::::::::::
　　　　　ヽ___,　　ﾆ／￣―――――￣￣::::::::＼ニ ___ノ　+　　　+　....:::::::::
　　　　　　ヽﾆ -‐（　　　　　　　　:::::::::::::::::::::::::::::::::≡ __ノ+　┼　＊:::::::::
　　　　　　　ヽ---＼＿＿::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;ノ＿　+　　┼　 .::::::::::
　:::::...　　　　　+　┼　+ 　　+　　　　ー-､___~'''''ー-､　　　:....::::::::::::
　　:::::::....　　　　　+　┼　　　　＊+　　　　　+~~'''ヽ　..:...::::::::::::::::::::
　　　:::::::::::::::::.....　　　　+ 　　＊　. 　　┼　　:....:::::::::::::::::
　　　　::::::::::::::::::::....:　+　＊　　　　 +　　　.....:::::::::::::::::

166 ：１３２人目の素数さん：04/09/16 14:49:05

>>164
> これが答だよと言われてそれが本当かどうかを検証する手間がPな問題をNP
答えが Yes か No の問題で NP でないものもあるよ．

167 ：１３２人目の素数さん：04/09/16 21:38:13

トランジスタさげ

168 ：１３２人目の素数さん：04/09/18 00:34:21

http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/demo/TSP/index.html

↑巡回セールスマン問題を確率的に解くデモンストレーション。
　けっこう速いんじゃないですか？誤差数パーセント以内ですし。

169 ：１３２人目の素数さん：04/09/18 00:37:13

↑誤差っていうのは最適解からの誤差ね。

170 ：１３２人目の素数さん：04/09/23 10:43:38

711

171 ：１３２人目の素数さん：04/09/23 14:13:43

Cas Stone Cold said so!!!!!!!

172 ：１３２人目の素数さん：04/09/23 14:16:25

>>165
アホウドリ

173 ：１３２人目の素数さん：04/09/28 05:49:11

812

174 ：１３２人目の素数さん：04/10/04 00:16:51

239

175 ：ぶんけいくん：04/10/07 18:51:17

守屋悦郎、「チューリングマシンと計算量の理論」をぺらぺらめくっています。
ほかにも日本語で読めるP=NP問題の基本文献があったら教えてください。

176 ：１３２人目の素数さん：04/10/12 23:45:23

774

177 ：ぶんけいくん：04/10/14 08:45:45

DL
NL
P
NP
PSACE
EXP

P vs NP問題はシプサの教科書読んでだいたい掴めたけど、
残りのDL NL PSPACE EXPってよく分かりません。
EXPは指数時間アルゴリズムってことだよね？
守屋さんの本、文系には難しいです。
誰かやさしく教えてちょ。

178 ：１３２人目の素数さん：04/10/19 03:38:13

462

179 ：１３２人目の素数さん：04/10/19 03:49:58

>>177
DL,NLのLはLOGSPACEの略かな。
時間じゃなくて記憶領域の大きさで測った計算量によるクラス。

180 ：ぶんけいくん：04/10/19 21:32:09

>>179

なるへそ。
計算に必要な時間(ステップ数)ではなく
領域(メモリ量)の問題ということですね。
ところで、いま計算量の階層の問題と
人工知能のフレーム問題との関連について調べているのですが、
双方に触れたお勧めの文献ってありますか？
どちらも有限の情報処理能力しかもたない人間＆コンピューターが
無限もしくはそれに近い指数時間アルゴリズムを扱おうとすることの
困難から生じるという意味で、
問題意識が共通してるのかしらん、と素人は思うのですが。

181 ：１３２人目の素数さん：04/10/24 09:46:56

711

182 ：１３２人目の素数さん：04/10/30 21:39:19

612

183 ：１３２人目の素数さん：04/11/04 21:47:33

497

184 ：１３２人目の素数さん：04/11/05 00:49:52

参考になります

185 ：１３２人目の素数さん：04/11/09 11:57:36

178

186 ：１３２人目の素数さん：04/11/14 14:54:30

数学の三大未解決難問は
Ｐ＝ＮＰ問題、
リーマンの予想、
ポアンカレの予想
ですね？

187 ：１３２人目の素数さん：04/11/14 14:59:05

P=NPな訳ないだろ
整数計画問題も多項式時間で解けるってのか？

188 ：１３２人目の素数さん：04/11/15 08:51:35

>>186
数学三大難問は
Ｐ＝ＮＰ問題
ホッジの予想
スタンダードの予想だろ？

189 ：１３２人目の素数さん：04/11/21 02:18:32

713

190 ：１３２人目の素数さん：04/11/21 02:50:33

>>180
あまり関係ない。

191 ：１３２人目の素数さん：04/11/27 14:28:26

748

192 ：１３２人目の素数さん：04/11/27 14:33:21

>>188
いい加減にやめれアホ

193 ：１３２人目の素数さん：04/12/04 23:52:24

436

194 ：山本エミ子 ◆YH4ME.Qywg ：04/12/05 18:21:30

Aは２行２列の行列。
固有値pに対する固有ベクトルの一つをu、固有値qに対する固有ベクトルの一つをvとする。
uとvの内積をu･vと表しAの転置行列をBとすると

(Au)･v=u･(Bv)

であることを証明せよ。

即出だと思いますが

だなたか証明してください。

よろしくお願します。

195 ：１３２人目の素数さん：04/12/05 18:45:34

>>194
氏ね、荒らし。

196 ：１３２人目の素数さん：04/12/08 02:46:49

大ニュースです。
韓国人数学者がＰ＝ＮＰ問題を解いたそうです。

http://bbs.enjoykorea.naver.co.jp/jaction/read.php?id=enjoyjapan_8&nid=987200&work=list&st=&sw=&cp=1

197 ：１３２人目の素数さん：04/12/08 04:41:44

>>196
>>72

似たような話が以前にもあったとは思ったが、
同一人物じゃねえか。

198 ：１３２人目の素数さん：04/12/14 23:07:22

770

199 ：１３２人目の素数さん：04/12/21 23:34:06

724

200 ：１３２人目の素数さん：04/12/23 19:54:23

素数判定じゃなくて？

201 ：１３２人目の素数さん：04/12/28 19:07:12

720

202 ：１３２人目の素数さん：04/12/31 23:32:30

てｓｔ

203 ：１３２人目の素数さん：05/01/01 11:30:17

age

204 ：１３２人目の素数さん：05/01/11 20:02:12

The Complexity Zoo
ttp://www.complexityzoo.com/

いろんなクラスが載ってます

205 ：１３２人目の素数さん：05/01/17 05:20:33

P≠NPが証明されたら、ある問題に対しては、
神は人間に延々とサイコロを振り続けることを強要したってことだよな？
何億年も手当たり次第に試してみる以外解けない問題もあるってことで。
だとしたら絶望して死ぬよ。マジで。そんな腐れ宇宙に存在してられるか。
本当にこの宇宙を作った奴はアホだろ。生物が発生すればいいってもんじゃねーっての。
クソッ！クソッ！最近のクソゲーの勘違いしたやりこみ要素みたいじゃねーか。
もう本気でブチキレですよ？ああもう最後の最後で全てを台無しにしてくれましたね。
じわじわとなぶり殺しにしてくれる！！
つーか馬鹿じゃねーの？P≠NPて。嫌がらせしたいだけだろうが。なぁ？
マジで姑息だな。なめきってる。明らかにおかしい。頭おかしいですよ。
悪意すら感じるね。お前ら馬鹿みたいに永遠にくじ引きでもしてろよﾌﾟｹﾞﾗｵﾌﾟｽて。
いくら計算してもお前らにはこの点はだせねぇよｗｗｗｗって。ああもう。

206 ：１３２人目の素数さん：05/01/18 10:05:13

それがわかっただけでも数学ってすごいじゃん

207 ：１３２人目の素数さん：05/01/19 02:19:26

仮にP≠NPが証明されたとしても、
「運が良けりゃ一発で解ける」という性質は、ずっと付いて回るから、
ちょうど角の三等分問題みたいに、
P＝NPにチャレンジする素人さんは後を絶たないんだろうな。

208 ：１３２人目の素数さん：05/01/19 02:31:26

ところで、ほとんどの専門家がP≠NPと予想しているらしいのだけど、
その根拠って何だろう？極端な話、１０乗オーダーでも１００乗オーダーでも
多項式時間では絶対に解けない、というのは何だかすごい話だ。

209 ：１３２人目の素数さん：05/01/31 21:57:35

組み合わせの爆発のまえでは多項式時間などへみたいなもんだ。
とても追いつかん。

210 ：１３２人目の素数さん：05/01/31 22:02:26

>>208
だから、予想なんだって。
どれだけやっても誰も解けないからおそらくそうなんだろう、っていう。

211 ：１３２人目の素数さん：05/01/31 22:10:25

俺も大学院のときはco-NP問題を研究してた。
証明システムを提案して鳩の巣原理が多項式サイズで
証明できることを示したもんだ。

212 ：１３２人目の素数さん：05/02/11 23:05:16

P=NP問題勉強するのに良い教科書教えて下さい

213 ：１３２人目の素数さん：05/02/11 23:12:04

　 ,j;;;;;j,. ---一､｀　―--‐､_ l;;;;;;
　｛;;;;;;ゝ T辷iﾌ i 　　f'辷jァ　 !i;;;;;　
　ヾ;;;ﾊ　　　　ﾉ　　　　　　　.::!lﾘ;;rﾞ　　そう言われていた時期も確かにありました
　　 `Z;i　　　〈.,_..,.　　　　　　ﾉ;;;;;;;;>
　　,;ぇﾊ、　､_,.ｰ-､_',. 　　,ｆﾞ: Y;;f
　　 ~''戈ヽ　｀二´ 　　 r'´:::.　`!

214 ：１３２人目の素数さん：05/02/11 23:37:37

俺も学部のころはNP≠Pなんて、俺が夏休みつぶしてまじで考えれば
案外解けるんじゃないかっておもってたよ。

215 ：１３２人目の素数さん：05/02/12 13:38:25

ｾｰﾙｽﾏﾝ
ｾｰﾙｽﾏﾝ

216 ：１３２人目の素数さん：05/02/12 23:46:52

sipser でも読んどけ

217 ：１３２人目の素数さん：05/02/13 01:57:04

ＰＣＰってどうよ？

218 ：１３２人目の素数さん：05/02/13 02:35:19

P=NPという公理を設けても矛盾がなく、P≠NPという公理を設けても矛盾が
ないというようなことがあれば面白いのに。

219 ：１３２人目の素数さん：05/02/13 17:25:40

>>216
計算理論の基礎のこと？

220 ：１３２人目の素数さん：05/02/15 13:56:53

>219
そう。
丁寧に書かれていて読みやすいよ。

>219 がアルゴリズム屋なら

Computers and Intractability
http://www.amazon.co.jp/exec/obidos/ASIN/0716710455/qid%3D1108443122/250-5488768-3266663

Complexity and Approximation
http://www.amazon.co.jp/exec/obidos/ASIN/3540654313/qid=1108443254/sr=1-3/ref=sr_1_8_3/250-5488768-3266663

なども良い。

221 ：１３２人目の素数さん：05/02/19 16:59:55

396

222 ：１３２人目の素数さん：05/02/19 17:06:39

お舞ら出す本が古すぎｗ
今業界でのはやりは、
Computability and complexity (Jones)

223 ：１３２人目の素数さん：05/02/20 22:06:27

>>218
独立でしたってか

224 ：１３２人目の素数さん：05/02/21 01:15:42

現実的な意味のある問題だからそれはないと思うが

225 ：１３２人目の素数さん：05/02/24 00:51:45

ハッシュテーブルを用いればO(1)で解けます。

Q.E.D.

226 ：１３２人目の素数さん：05/02/24 06:25:08

age

227 ：１３２人目の素数さん：05/03/06 13:53:49

583

228 ：１３２人目の素数さん：05/03/06 14:10:12

>>225
ハッシュ関数の実装によるけんね

229 ：１３２人目の素数さん：05/03/16 23:14:16

899

230 ：１３２人目の素数さん：05/03/16 23:22:34

このスレは後で読むつもりだが、これを解くのは数学者だろうか？

231 ：１３２人目の素数さん：05/03/17 03:31:28

チューリングマシンは一応数学モデルだから

232 ：１３２人目の素数さん：2005/03/29(火) 01:13:45

702

233 ：１３２人目の素数さん：2005/04/08(金) 11:20:56

未解決問題でもリーマン予想とかに比べたら、P≠NP問題は価値が低いと思う

234 ：１３２人目の素数さん：2005/04/08(金) 22:11:53

>>233
もしまんがいち
P=NP
だったなら実社会への影響はすさまじい
（P≠NPだろうと多くが人が考えているので）

235 ：１３２人目の素数さん：2005/04/11(月) 09:21:11

P=NPなら、たんぱく質の構造がアミノ酸の１次配列から簡単に決めれるし、
CPU等の配線も最適なものが簡単に見つけられるし、多分万能メイドロボも実現できるし
もう人類マンセー！な明るい未来が実現できる。

236 ：１３２人目の素数さん：2005/04/22(金) 11:40:03

>>235
じゃあ、素数判定がP問題で、素因数分解もP問題だから公開鍵式暗号は既に崩壊してるんだね！！

237 ：１３２人目の素数さん：2005/04/22(金) 20:08:11

>236
それでもまだNP-hard baseの公開鍵暗号は崩壊せんよな。
実用的では無いが、あるぞ。

238 ：１３２人目の素数さん：2005/04/23(土) 13:38:57

>>237
基本的に暗号を解く問題はNPに入るだろ．だからそういうのもNP=Pなら崩壊するぞ．
秘密鍵をもらって多項式時間で復号できない暗号なんて意味がない．

239 ：１３２人目の素数さん：2005/04/25(月) 20:59:46

age

240 ：１３２人目の素数さん：2005/04/25(月) 21:08:17

NP=Pでも、その方法がわからないと意味ないじゃん。

241 ：１３２人目の素数さん：2005/04/26(火) 02:12:57

山口人生様のスレはここですか？

242 ：１３２人目の素数さん：2005/04/26(火) 15:55:41

>>236
＞素因数分解もP問題
いつこんなことが示されたんだ？

243 ：１３２人目の素数さん：2005/05/11(水) 21:29:46

959

244 ：BlockKnightOffline ◆yPnpjLO5jE ：2005/05/11(水) 21:48:10

P=NPなら空間を折りたたみ、情報が光速を超えることが可能に。(惑星間旅行の実現）
オレの予想によれば、P=NPは成り立つ。

245 ：P=NP問題を解きました。：2005/05/25(水) 14:35:27

Nについての一次方程式として解けばよい。

P=NP⇔1=N

これでチューリングを超えたな。

246 ：245：2005/05/25(水) 18:09:45

ついでに山口人生も超えたな。

「計算測度理論の存亡　P=NP問題の解決」という本を出せそうだな。
山口人生よ，船井ベストペーパー賞を出すのはこの私だ。

247 ：１３２人目の素数さん：2005/05/26(木) 23:02:46

>>245
まさか両辺をＰで割ったとか？
Ｐが０のときどうする。

248 ：１３２人目の素数さん：2005/05/27(金) 01:07:24

P=0ならば、任意のNについてP=NPが成り立つ

249 ：１３２人目の素数さん：2005/05/27(金) 06:58:17

両辺をPで割るのは既出もいいところ。
ちょうど今ﾔﾌ掲示板で同じ事を言ってる
馬鹿がいるし。

250 ：245：2005/05/27(金) 09:50:38

>>249
てかこのスレでも外出だし。

相変わらず人生痰が活躍しているので，ちょっと・・・ね。

251 ：１３２人目の素数さん：2005/05/27(金) 19:40:10

＞てかこのスレでも外出だし。

だから、そう言われてるんだろうが。

252 ：１３２人目の素数さん：2005/05/31(火) 22:56:15

何か手掛かりになる成果。失敗した試みとかってどんなものがあるの？

253 ：１３２人目の素数さん：2005/06/01(水) 00:38:36

>>251
「そとだし」って読んでもた。

254 ：１３２人目の素数さん：2005/06/01(水) 00:52:44

チューリングマシンで表現可能なものと不可能なものとを区別するだけだろ?
鍵は、ヒルベルトがぼけていてで、イデアルの先に答えがあることを見抜くことだ。
不完全性定理も同時に解ける。

255 ：245：2005/06/01(水) 01:04:27

という夢をみたんだが。

256 ：１３２人目の素数さん：2005/06/26(日) 00:42:16

188

257 ：１３２人目の素数さん：2005/07/16(土) 04:46:01

素因数分解はNP完全だと示されているわけでもないから
そいつがP問題になっても面白くはない。
やはり男のロマンはNP完全の代表格TSP。

258 ：１３２人目の素数さん：2005/07/16(土) 23:52:00

PNP

NPN

259 ：１３２人目の素数さん：2005/07/20(水) 12:22:24

トランジスタかよ

260 ：１３２人目の素数さん：2005/07/21(木) 23:53:15

P型、N型か(w

261 ：１３２人目の素数さん：2005/07/23(土) 05:27:04

age

262 ：１３２人目の素数さん：2005/07/23(土) 13:02:30

二年。

263 ：１３２人目の素数さん：2005/07/24(日) 16:44:14

L＝NLが証明されてるって本当ですか？

264 ：１３２人目の素数さん：2005/07/25(月) 10:22:05

>>263
L=SLでないの？

265 ：sage：2005/07/28(木) 21:44:56

>>263
グラフのパスを求める問題(NL完全)がLで解けるって聞いたことあるけど。

>>264
SLって何？

266 ：１３２人目の素数さん：2005/07/28(木) 23:30:25

>265
ノ http://www.complexityzoo.com/#sl

267 ：１３２人目の素数さん：2005/07/28(木) 23:37:37

>>266
なんじゃこれは
クラス多過ぎwww

268 ：１３２人目の素数さん：2005/07/29(金) 00:23:19

>>265
残念ながらそれは264がいってるL=SLだ

269 ：１３２人目の素数さん：2005/07/31(日) 01:51:49

質問していいのか分かんないけど…　悩んでるのでお願いします。
「問題AがNP困難である」というとき，その定義から，AはNPに属するとは限りませんよね。
そんな問題って例えばどんなものがあるんですか？

270 ：１３２人目の素数さん：2005/07/31(日) 02:01:17

自己レスですが…
そんな問題が見つかる，ということは，P=NPが証明される，という理解でよいのでしょうか。

271 ：１３２人目の素数さん：2005/08/01(月) 21:31:55

>>269
NP困難でかつ決定不能な問題があります

272 ：１３２人目の素数さん：2005/08/01(月) 23:40:00

269
決定不能ということは…　
「非決定的計算機を用いたとしても多項式時間で解けない」ってことですか？

273 ：１３２人目の素数さん：2005/08/04(木) 07:51:39

age

274 ：１３２人目の素数さん：2005/08/04(木) 20:21:49

>>272
それは初歩の初歩だろ・・・
決定性TMで決定不能な問題は非決定性TMでも決定不能だよ

275 ：１３２人目の素数さん：2005/08/05(金) 00:38:39

>>269 >>270
数え切れないほどあるよ．そもそも充足可能性問題(SAT)とかは
NP完全(NPかつNP困難)だし．NP困難な問題がPに属することが
示されればNP=Pにはなる．

276 ：269：2005/08/05(金) 04:23:11

すいません。そもそも僕が，
「非決定的計算機も用いても解くことさえできない問題がある」
ってことを知らなくて，変なこと書いてしまいました。

>275
SATはNPなんだから，269の条件には当てはまらないのでは…？

277 ：１３２人目の素数さん：2005/08/05(金) 09:49:37

>>269はNP困難な問題があるかどうか？という質問だから
SATがNP困難だよって言っているのでは？

278 ：269：2005/08/06(土) 01:04:34

いや，>269では，
「NP困難であるがNPではないような問題A」の問題例が知りたかったんです。

279 ：１３２人目の素数さん：2005/08/06(土) 01:16:27

age

280 ：１３２人目の素数さん：2005/08/06(土) 01:52:31

Problems is No-Problems.
どんな困難も問題にはならない。なぜなら僕らはそれを解くから。
どんな問題も解けないということはない。なぜなら人類はそれを乗り越えていくから。

P=NP∴人類は光速を超える。時間を遡り過去へも行ける。どこまでも遠くへ。

281 ：１３２人目の素数さん：2005/08/06(土) 02:13:16

「P=NP」とは「解法」を知ることッ！「公式」を我が物とすることじゃあッ！
P=NPは「数学」の賛歌ッ！！
数学のすばらしさは勇気のすばらしさ！！
いくら強くてもチューリング・マシンは「勇気」を知らん！
ノミと同類よォーッ！！

282 ：１３２人目の素数さん：2005/08/06(土) 23:25:57

ANAL問題

283 ：１３２人目の素数さん：2005/08/07(日) 00:46:34

>>278
計算可能で無い問題を探せば、皆そうだと思います。

また、予想（未証明）でいいなら、PSPACE完全、EXP完全な問題を探せばいい
のでは？

しかし、それら問題が、NPに属さないことを証明せよというと恐ろしく難
しい。
多くの研究者が挑戦して討ち死にしております。

284 ：１３２人目の素数さん：2005/08/07(日) 06:36:32

計算量クラスＡとＢの区別は、Ａ完全問題がＢ完全問題に
「多項式時間で」還元可能か否かで決まる、というのが暗黙の前提。

285 ：１３２人目の素数さん：2005/08/10(水) 22:01:19

任意の自然数ｎに対しｎ変数３SATをｎの多項式時間でとくアルゴリズムが存在する。
これを証明しますた。

286 ：１３２人目の素数さん：2005/08/10(水) 23:19:43

age

287 ：１３２人目の素数さん：2005/08/11(木) 10:28:08

それは既に証明されてるよ

288 ：ゲームバカ：2005/08/16(火) 21:11:31

>>269
計算量の入門書でよいので、ちゃんと読んで
NP困難とNPの定義を理解するのがよい。理解すれば、いくらでも見つけられるよ。
（というか、入門書だと例として載っていたりするけど。。）

289 ：１３２人目の素数さん：2005/08/19(金) 08:33:03

age

290 ：１３２人目の素数さん：2005/08/23(火) 06:53:57

ここで質問するのが適切かどうかわかりませんが、
◆ わからない問題はここに書いてね１７２ ◆ から誘導されてきました。

P≠NPとして、ある問題AがNPに属するとします。
Aを解く多項式時間アルゴリズムが存在しないことを示したいんですが、
AがNP完全であることを示す意外に方法はありますか？

291 ：１３２人目の素数さん：2005/08/23(火) 10:34:34

290
P≠NPといった強力な仮定を設定しないとむずかしいと思う。何の仮定もなしに、多項式時間を越える下界を示せた問題自体ほとんどない覚えが。

292 ：１３２人目の素数さん：2005/08/23(火) 20:28:14

290
言い忘れ。AがNP完全である気がするのであれば、AがNP完全であることを示すのが労力低。

293 ：290：2005/08/24(水) 11:45:27

なるほど。
つまり方法はなくはないかもしれないが、
少なくともこんな質問をしている俺には無理だろうってことはわかりました。
どうもありがとうございました。

294 ：１３２人目の素数さん：2005/08/26(金) 22:52:09

P=co-NPならP=NPといえますか？

295 ：１３２人目の素数さん：2005/08/28(日) 02:35:15

ナトリウムとリン２つずつあっても一酸化炭素ができるわけではない

296 ：１３２人目の素数さん：2005/08/28(日) 04:04:46

おまえﾂﾏﾝﾈ

297 ：１３２人目の素数さん：2005/08/28(日) 04:15:36

>>294
既出かと思われますが、以下の２式は成立します。
① P＝NP ⇒ NP＝co-NP
② NP≠co-NP ⇒ P≠NP
しかし、矢印の逆方向が成立するかどうかは不明です。

298 ：１３２人目の素数さん：2005/08/28(日) 10:08:53

①も②も未解決かと思ったけど。
文献ある？

299 ：１３２人目の素数さん：2005/08/28(日) 19:51:04

>>298
もちろんP＝NP？もNP≠co-NP？も未解決ですが、
「もしも成立すれば」⇒の先も成立するという意味です。
(P＝co-Pが成立するから)

300 ：たびたびスマン：2005/08/28(日) 20:05:21

>>294もちろんP=co-NPならP=NPといえます。

301 ：298：2005/08/29(月) 21:39:42

>>299
もしも成立すれば、という意味なのはわかってるんだけど。
①も②もそんなに明らかな定理じゃないよね。

302 ：１３２人目の素数さん：2005/08/30(火) 00:14:05

>>301えっ、そうなの？とりあえず文献をあげるけど。
「計算量理論概説」朝倉書店より。
①(144ページ)定理4.12
P＝NPならば、多項式時間階層がi＝1の段階でつぶれてNP＝co-NPとなる。
②(132ページ)より引用
…実際、NP≠co-NPが成り立つとすればP＝co-PなのであるからP≠NPが成り立つことになる。

303 ：１３２人目の素数さん：2005/08/30(火) 01:26:59

1. P=NP なら NP 完全問題を解く多項式時間決定性のプログラムが存在するが、
これは入力に対して、必ず yes か no を答えることになる。
したがって yes と no を取り替えれば co-NP を解くプログラムになる。
つまり NP=co-NP

2. は単なる 1 の対偶。

逆方向は未解決です。

304 ：298：2005/08/30(火) 20:47:54

P=NPが成り立つとき言えることはNP完全問題に対して
多項式時間でyesかnoを答えてくれる、ではなく
yesの時に多項式時間で答えてくれる（noのときは指数時間かかっても
しらんぷり）だと思うのですが。
僕の勘違いでしょうか。

305 ：１３２人目の素数さん：2005/08/30(火) 21:48:15

ヒント：P=co-P

306 ：１３２人目の素数さん：2005/08/30(火) 22:09:37

>>304
とにかくP＝NPならば、すべてのNP問題がP問題でもあるということです。
すべてのP問題がNP問題でもある、というのは現時点で当然のことです。

307 ：１３２人目の素数さん：2005/08/30(火) 22:54:32

304:298 08/30(火) 20:47 [sage]

P=NPが成り立つとき言えることはNP完全問題に対して
多項式時間でyesかnoを答えてくれること。

↑そうです。そういうアルゴリズムが存在するということです。

yesの時に多項式時間で答えてくれる（noのときは指数時間かかっても
しらんぷり）だと思うのですが。
僕の勘違いでしょうか。

↑しらんぷりされるようなら、それはPではないのですが。
何を勘違いなされているのですか？

308 ：１３２人目の素数さん：2005/08/30(火) 23:14:35

>>304
ようするに、決定性TMの世界でP＝NPが成立するかどうかが大問題なわけです。
非決定性TMの世界ではP＝NPは自明に成立します。

309 ：１３２人目の素数さん：2005/08/31(水) 09:49:08

>>308
> 決定性TMの世界でP＝NPが成立するかどうかが大問題なわけです。
> 非決定性TMの世界ではP＝NPは自明に成立します。

決定性TMの世界，非決定性TMの世界ってどういう意味ですか？
Pは決定性TMで定義されて，NPは非決定性TMで定義されるの
だけども，ここでの非決定性TMの世界のPって何を指しているの？

310 ：１３２人目の素数さん：2005/09/01(木) 19:47:37

こんなの見つけました。
http://arxiv.org/abs/cs.CC/0502030
NP!=Pが証明されたみたいだけどほんとかな？

311 ：１３２人目の素数さん：2005/09/01(木) 21:28:16

Pop = NiPpon

312 ：１３２人目の素数さん：2005/09/01(木) 22:31:53

>>310
誰か検証してくれ。漏れにはわからん。

313 ：１３２人目の素数さん：2005/09/02(金) 00:45:42

>>310
メールアドレスを見た時点でかなり期待薄。

314 ：１３２人目の素数さん：2005/09/02(金) 09:42:04

こんなサイトもあるぞな。

The P-versus-NP page
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

このサイトによれば、
「P=NP」「P!=NP」「決定不能」
は、すべて証明済みだそうだ(笑)

315 ：１３２人目の素数さん：2005/09/02(金) 22:57:45

いつのまに・・・.nl ってことはオランダ人か。しょーがねぇーなー、海面より低い所に棲んでるからそーゆーよくわからないことをくちばしるようになっちゃうのかな(w

316 ：１３２人目の素数さん：2005/09/03(土) 01:54:21

>315
そのオランダ人は信じてないと思うぞ。

> I am interested in extending this list.
> If you know of other papers in this area, then please send me the links.

あの人の結果が無いので、誰か知らせてあげるといいんじゃないかw

317 ：１３２人目の素数さん：2005/09/03(土) 07:58:55

そこはトンデモをヲチして楽しんでるサイトだろ

318 ：１３２人目の素数さん：2005/09/03(土) 11:16:48

そうなのか、すまんな。海面より低いところに棲んでるからって馬鹿にしてスマソ！

319 ：１３２人目の素数さん：2005/09/03(土) 17:55:38

もしかすると量子コンピュータの上ではP=NPかもしれないね。

320 ：１３２人目の素数さん：2005/09/03(土) 18:00:38

>>319
QTM上でP=NPかどうかという問題は今までさんざん研究されてきた未解決問題ですよ

321 ：１３２人目の素数さん：2005/09/04(日) 00:25:36

>>319-320
PとかNPはQTMでは定義されてないので･･･
BQP⊇NP
かどうかは未解決

322 ：１３２人目の素数さん：2005/09/05(月) 22:39:20

ネタも無いようだしみんなでSATでも解かんかね。
http://www.intellektik.informatik.tu-darmstadt.de/SATLIB/benchm.html

323 ：１３２人目の素数さん：2005/09/22(木) 01:14:33

そういや >>104 のLie代数つかって云々って
結局解けてなかったの？

324 ：１３２人目の素数さん：2005/09/23(金) 18:20:32

age

325 ：１３２人目の素数さん：2005/10/08(土) 15:06:53

631

326 ：１３２人目の素数さん：2005/11/01(火) 23:37:42

トートロジーをSATに多項式時間で帰着できるとき
co-NP=NPが成り立つと思うのですが、その逆は成り立つのでしょうか。
つまりco-NP=NPが成り立つならばトートロジーをSATに多項式時間で
帰着させるアルゴリズムが存在するといえますか？

327 ：１３２人目の素数さん：2005/11/02(水) 00:55:54

いえます

328 ：１３２人目の素数さん：2005/11/02(水) 07:58:33

山口人生様が解決済み。
いまさら何を言っているんだ？

329 ：１３２人目の素数さん：2005/11/18(金) 11:00:31

163

330 ：１３２人目の素数さん：2005/12/03(土) 22:45:51

多項式時間で十分高い確率でNP完全問題の解を見つけられるが
解がなかったときは停止しない。というアルゴリズムが
見つかったとき、P＝NPであるといえますか？

331 ：１３２人目の素数さん：2005/12/03(土) 23:23:15

それだけだとBPP⊇NPではないでしょうか。
さらにBPP=PがいえればNP=Pだと思います。
BPP=Pだとは強く予想されていますが。

332 ：１３２人目の素数さん：2005/12/05(月) 13:59:19

age

333 ：１３２人目の素数さん：2005/12/05(月) 22:09:12

Complexity Zoo とか見ると絶望的な気分になる

334 ：１３２人目の素数さん：2005/12/23(金) 18:34:50

BPPを計算する計算機は実在するってことでOK?

335 ：１３２人目の素数さん：2005/12/23(金) 19:25:00

>>334
確か疑似乱数を使っても BPP の能力が落ちないという結果があったはずなので、
Okでしょう。
# PP はだめだけど。

336 ：１３２人目の素数さん：2005/12/30(金) 18:39:31

CPUのマルチコア化が進んでいるが、そのうちコアがめちゃめちゃふえて
実質非決定性の計算もできるようにならないかな。

337 ：１３２人目の素数さん：2005/12/31(土) 10:40:39

>336
コアが1000個になったとしても、
その計算能力はコア一つの場合の1000倍以上には
（本質的には）ならないだろうし、
一方で、非決定性の計算は計算量がインスタンスのサイズに対して
指数的に増えていくから絶望的だと思う。

>335
>確か疑似乱数を使っても BPP の能力が落ちない
それって「擬似乱数」の定義に依存するよね？
その証明で使われている擬似乱数が実在の計算機で生成できるか、
っていう話になるんじゃないかな？

338 ：１３２人目の素数さん：2005/12/31(土) 14:34:43

【かっこ悪い】建部崩れ、見参！【情けないｗ】
http://science4.2ch.net/test/read.cgi/math/1135765594
【夢vs】結果を出せば職はある？ｗ【現実】
http://science4.2ch.net/test/read.cgi/math/1134888899
【事実】研究しても、ポスト無し！【愕然】
http://science4.2ch.net/test/read.cgi/math/1134089493
関連：【建部】斎藤毅先生【Invent】
http://science4.2ch.net/test/read.cgi/math/1134743220

339 ：１３２人目の素数さん：2006/01/02(月) 05:14:46

633

340 ：１３２人目の素数さん：2006/01/02(月) 20:50:40

つかぬことをお聞きしますが、擬似乱数、擬似乱数、
っていってますけど真の乱数は計算できないてことですか？

341 ：１３２人目の素数さん：2006/01/02(月) 23:39:14

>>340
定義を調べてごらん。
計算できるなら乱数ではないでしょ。

342 ：１３２人目の素数さん：2006/01/03(火) 12:25:24

乱数が計算できないことって証明されてるの？
乱数列 R(n) について R(n+1)がR(1)...R(n)だけの情報から計算不可能ならいいんじゃない？

343 ：１３２人目の素数さん：2006/01/03(火) 15:22:06

>>340
チャイティンの「知の限界」「数学の限界」あたりを読まれるとよろしいかと・・・

344 ：１３２人目の素数さん：2006/01/03(火) 16:09:31

いくら言っても全然読まない予感

345 ：340：2006/01/03(火) 19:17:53

>>343
>>344
ゲーデルの読み物とかチョロッと見てみましたが、
ぜんぜん訳わかりませんでした。
とほほ。こんな私でも何とかなりますかね？

346 ：１３２人目の素数さん：2006/01/03(火) 22:16:56

無理だろ
あきらめろ

347 ：１３２人目の素数さん：2006/01/03(火) 23:30:43

まさに「痴の限界」(w

348 ：１３２人目の素数さん：2006/01/05(木) 04:44:38

＞342
コロモゴルフ式の乱数列の定義とは、その無限列の充分に長い部分列を
取り出して来た時に、それを計算する手順をどのように作ったとしても
その記述が乱数の列をそのまま書き並べるよりも長くなる、そうなる
ような数列のこと。つまり記号列の情報として如何にしても圧縮でき
ないような数列のこと。
だから、この定義によれば無限に続く乱数列は有限長のプログラムでは
生成できないことになる。つまり有限の決定的アルゴリズムでは発生
することは出来ないものである。

349 ：１３２人目の素数さん：2006/01/08(日) 23:44:59

ttp://math.bbs.thebbs.jp/1123581360/17

バカ発見w

350 ：１３２人目の素数さん：2006/01/10(火) 10:14:30

age

351 ：１３２人目の素数さん：2006/01/16(月) 15:04:33

まだ続いているのか。
山口人生様の仕事も理解できないレベルの猿の戯言。
「Ｐ＝ＮＰ？」問題は山口人生様が解いた。
東大の馬鹿を筆頭に、トンデモと思うのがアホの証拠。

352 ：１３２人目の素数さん：2006/01/16(月) 23:03:47

残念、ここは先生のためのスレではありませんよ。
がんばって探してくださいね(^^)

353 ：１３２人目の素数さん：2006/01/18(水) 12:06:38

それで、マジメに「Ｐ＝ＮＰ？」問題を語っているつもりか？
素人馬鹿の群れ。

354 ：１３２人目の素数さん：2006/01/18(水) 16:12:16

P=NP
両辺をPでわる
1=N
よって
P≠0のときN=1
P=0のときNは任意

と釣ってみる

355 ：１３２人目の素数さん：2006/01/18(水) 17:57:13

>>354
>>78

356 ：１３２人目の素数さん：2006/01/18(水) 18:06:59

マジレスすると
P-NP=0
因数分解して
P(1-N)=0
P=0,1-N=0
よってP=0又はN=1

357 ：１３２人目の素数さん：2006/01/21(土) 15:46:07

P=NP問題に繋がる、最も簡単な問題を教えてください。

358 ：１３２人目の素数さん：2006/01/21(土) 15:53:06

SAT

359 ：１３２人目の素数さん：2006/01/21(土) 16:55:45

NP∩co-NPに属してPに属することが知られていない問題を教えてください。

360 ：１３２人目の素数さん：2006/01/22(日) 01:20:46

>359
マイナーだがSVP_√nとかどうだろう.
格子の次元をnとして近似度√nの最短ベクトル問題.
これの判定版がNPかつcoNP.

361 ：１３２人目の素数さん：2006/01/22(日) 11:24:14

つParity Game

362 ：１３２人目の素数さん：2006/01/23(月) 22:17:58

>>360
>>361
ありがとうございます。
ゆっくり調べてみます。
ところでNP∩co-NP完全問題というのはあるのでしょうか。

363 ：１３２人目の素数さん：2006/02/02(木) 00:27:53

こんなのあったよ。
http://64.233.179.104/search?q=cache:1W6M-yNlirQJ:www.brics.dk/RS/00/19/BRICS-RS-00-19.pdf+np+%E2%88%A7%E3%80%80conp&hl=ja&gl=jp&ct=clnk&cd=2

364 ：１３２人目の素数さん：2006/02/02(木) 00:52:46

＞３６２
＞ところでNP∩co-NP完全問題というのはあるのでしょうか。
http://qwiki.caltech.edu/wiki/Complexity_Zoo#npiconp
には
(NP∩co-NP) Is not believed to contain complete problems.
とあるね。

＞３６３
それは NP と co-NP/poly との intersection だから、NP∩co-NPとは違うよ。

365 ：１３２人目の素数さん：2006/02/02(木) 16:07:15

age

366 ：１３２人目の素数さん：2006/02/05(日) 08:58:21

pnp

367 ：１３２人目の素数さん：2006/02/05(日) 08:59:01

483

368 ：１３２人目の素数さん：2006/02/23(木) 01:02:46

PvsNP問題に対角論法が使えないという奴だけど、あれって
「オラクルが存在するなら対角論法は使えない」というだけじゃないか？
つまり「オラクルは存在しないので対角論法は使えないとはいえない」
ということになると思うんだが・・・

369 ：１３２人目の素数さん：2006/02/23(木) 02:20:31

age

370 ：１３２人目の素数さん：2006/02/23(木) 10:47:51

>>368
もう少しくやしく

371 ：１３２人目の素数さん：2006/02/26(日) 20:59:13

漏れの本にはオラクルは存在すると書いてあるが。

372 ：１３２人目の素数さん：2006/02/26(日) 21:26:24

もしかしてオラクルは存在しないって言ってるのはある計算を
一ステップで実行するようなの計算機が実在しないってこと
をいってる？それは全然的外れのような。

373 ：１３２人目の素数さん：2006/02/26(日) 21:38:35

入力を読み込むのに線形時間はかかるんだから少なくとも線形時間はかかるだろ

374 ：１３２人目の素数さん：2006/02/26(日) 22:08:58

>>373
そんな餌に(ry

375 ：１３２人目の素数さん：2006/02/26(日) 22:27:08

オラクルをTMで作れるならP=NPで確定

376 ：１３２人目の素数さん：2006/02/26(日) 23:56:55

ここで恒例の

N=1

377 ：368：2006/02/27(月) 00:33:32

お、レスがついてる

オラクルTMではP=NPとP≠NPが両立するから対角論法は使えないってのはわかるけど
オラクルを使用しない普通のTMでP=NPとP≠NPが両立するという訳じゃないし
PvsNP問題に対角論法が使えないという証明にはなってないような気がするんだが・・・・

378 ：368：2006/02/27(月) 00:35:43

>>371
オラクルが存在するならオラクルTM⊂TMになるのでは？

379 ：１３２人目の素数さん：2006/02/27(月) 10:09:50

>>377
オラクル使わずに仮に対角線論法でP≠NPが言えたら任意のオラクルA
に対してP^A≠NP^A が言えるから矛盾．

380 ：１３２人目の素数さん：2006/02/27(月) 10:49:12

補足．矛盾するというのは
あるオラクルBが存在してP^B=NP^B
という定理にね．

381 ：368：2006/02/27(月) 12:07:21

P≠NPならばP^A≠NP^Aというわけではないのでは？
NPに属する問題がP＾Aに属する場合もあるし

382 ：１３２人目の素数さん：2006/02/27(月) 13:16:10

>>381
「対角線論法で」というのがポイント．

383 ：368：2006/02/27(月) 13:40:29

>>382
その違いが分からないです・・・
ＰとＮＰがＺＦＣから独立でないならば対角論法をつかってもつかわなくても
P=NPと仮定すると矛盾が生じるのは変わらないと思うんですが・・・

384 ：１３２人目の素数さん：2006/03/01(水) 22:26:02

age

385 ：１３２人目の素数さん：2006/03/03(金) 23:47:26

>>383
詳しく。

386 ：１３２人目の素数さん：2006/03/04(土) 00:11:37

N=1

387 ：１３２人目の素数さん：2006/03/04(土) 08:22:21

P=NP自身が決定不能問題である可能性はないのか？

388 ：１３２人目の素数さん：2006/03/04(土) 15:27:15

>>383
厳密には対角論法が使えないわけじゃない
それにZFC独立は証明されてない

>>387
当然ある
どっかの国際シンポジウムでアンケート取ったところ数パーセントの人はがそう考えているらしい
ただ、P=NPの場合他の集合論の問題に比べてきわめて具体的事例を扱っているので
ほとんどのひとは決定可能だと考えている

389 ：１３２人目の素数さん：2006/03/04(土) 20:41:02

ここらでひとつＮＰ完全問題を解くプログラムをみんなでインプリメントして見ませんか。

390 ：１３２人目の素数さん：2006/03/04(土) 22:37:39

P≠0ならN=1だし、P＝0ならNはすべての複素数じゃね?

391 ：１３２人目の素数さん：2006/03/09(木) 17:05:05

>>390
なあ、ちょっと引っ込んでてくれんか。

392 ：１３２人目の素数さん：2006/03/10(金) 01:03:52

>>390
ワンパターンすぎてつまらん。もっとひねれ

N=1

393 ：１３２人目の素数さん：2006/03/11(土) 00:41:19

意表をついてN≠1

394 ：１３２人目の素数さん：2006/03/14(火) 14:44:23

半導体の世界では、ＰＮＰはＮＰＮと並んで非常に重要であります。

395 ：１３２人目の素数さん：2006/03/14(火) 23:34:49

>>394
そう考えりゃP=NPなんてウソじゃん

396 ：１３２人目の素数さん：2006/03/20(月) 21:44:37

ね氏gnik

397 ：GiantLeaves ◆6fN.Sojv5w ：2006/03/20(月) 21:55:58

talk:>>396 お前に何が分かるというのか？

398 ：１３２人目の素数さん：2006/03/20(月) 22:02:49

典型レスって
・P=NP⇒1=N
・窒素と燐
・半導体(上と同じだが)
の他に何がある？

399 ：１３２人目の素数さん：2006/03/22(水) 09:49:41

しぇいくすぴあ
To P, or Not to P.

400 ：hamlet：2006/03/22(水) 13:37:13

That is the question.

401 ：１３２人目の素数さん：2006/03/22(水) 18:44:24

ﾜﾛﾀｗｗ

402 ：１３２人目の素数さん：2006/03/22(水) 19:31:50

素因数分解をＳＡＴに多項式時間帰着させたいんですが、どうすればいいですか？

403 ：１３２人目の素数さん：2006/03/22(水) 21:18:37

2進数表記してからCookの定理に従って記述すればいい

404 ：Pなのか、Pでないのか：2006/03/22(水) 22:03:07

>>399は、主語を all of NP と解釈すれば、文法的にも意味的にも
正しい問いかけになる、という事に今更ながら気付いた。

…わざわざ Not と大文字で書く必要はなかったのか
ハムレット難しすぎorz

405 ：１３２人目の素数さん：2006/03/22(水) 22:16:29

うまいな、と一瞬思ったけど

To P, or not to P
っていうようにPを動詞にすると
「おしっこするか否か、それが問題だ」
って下ネタになっちゃうな

406 ：１３２人目の素数さん：2006/03/26(日) 15:00:34

407 ：１３２人目の素数さん：2006/03/27(月) 15:32:54

NP完全問題を多項式時間で解くアルゴリズムを見つけてしまったんだけどどうすればいいの？
今度3年生になるので研究室に配属される来年まで待ってから教授に見せればいいかな？

408 ：１３２人目の素数さん：2006/03/27(月) 15:50:06

あらゆる類のNP完全問題を多項式時間内に解けるアルゴリズムっていうこと？

409 ：１３２人目の素数さん：2006/03/27(月) 15:51:45

NP完全問題であるハミルトン閉路問題を多項式時間で解けるので
ハミルトン閉路問題に帰着させればすべてのNP完全問題が多項式時間で解けるはずです

410 ：１３２人目の素数さん：2006/03/27(月) 15:52:49

山口人生超教授に見せればいいと思うよ

411 ：１３２人目の素数さん：2006/03/27(月) 16:01:21

>>407
まず、きちんと多項式時間で解けることを数学的な記述で証明して
普通の学会誌に載っているような記事並に読みやすい状況に論文を整理する。
ありがちなP=NP論文は最後の詰めを濁していて、そこに指数時間かかったりするものも
あるから、場合分けとかに隙がないように定理をきちんと証明する。
整理できたら、本屋とかで NP 完全関連の教科書を書いている先生をリストアップする。
気に入った先生に証明のアイディアと面会の申込のメールをする。
面会にこぎつけたら実際にあったら論文を見せながら説明し、どこの学会に
投稿するか相談してみよう。

412 ：１３２人目の素数さん：2006/03/27(月) 16:45:21

論文の書式とか投稿の仕方とかが分からないので研究室に配属されるのを待って
卒論にしようかと思います。どうせ再来年には卒論を書く事になるので

ε-δ論法で解いているので nが∃N_0より大きい場合しか使えず実用性は0な解法ですが・・・

413 ：１３２人目の素数さん：2006/03/27(月) 17:13:28

ｗ

414 ：１３２人目の素数さん：2006/03/27(月) 18:06:52

>>412
行列の積の高速化の話で70いくつかか80いくつかの行数がいるのもあるし、
別に実用性は全然問題ありません。素数判定の多項式時間の判定も結構遅いし。
発表すればきっと誰かが改良してくれる。

でも、関連論文の調査とかやることは多いのでそこから始めるべき。
本当に解けているなら世界中で同じ解法を何人も思い付いていることもあるから、
早く形にすべきだと思う。

415 ：１３２人目の素数さん：2006/03/27(月) 18:47:57

(´∀｀)

416 ：１３２人目の素数さん：2006/03/27(月) 18:49:38

>ハミルトン閉路問題に帰着させれば

そんなの何とでもいえる。
本質的にはただハミルトン閉路問題だけを解くアルゴリズムじゃないか？
しかしもしそれができたらNP完全問題⇔ハミルトン閉路問題が証明できる。。。

と素人が言ってみるテスト。

417 ：１３２人目の素数さん：2006/03/27(月) 20:46:09

age

418 ：１３２人目の素数さん：2006/03/27(月) 20:59:41

正ｎ面体上のハミルトニアンクローズドパス問題

419 ：１３２人目の素数さん：2006/03/28(火) 00:23:37

人生痰スレが埋まったため、こちらに迷惑がかかるおそれがありますが
どうかご容赦ください。

420 ：１３２人目の素数さん：2006/03/28(火) 00:54:36

注意！注意！注意！注意！注意！注意！

人生スレは永久廃止になりました。皆さん立てないでください。
もし立ったらそれは本人が立てたという証拠です。

注意！注意！注意！注意！注意！注意！

421 ：１３２人目の素数さん：2006/03/28(火) 01:08:03

予言。

P=NP かつ P≠NPです。
肯定的解決と否定的解決が同時になされます。
2009年ごろ。

422 ：１３２人目の素数さん：2006/03/28(火) 07:40:26

>>419
早速変なの沸いてるじゃねーか。
責任もってとっとと厨収容所立ててこい。

423 ：１３２人目の素数さん：2006/03/28(火) 16:07:41

彼は自分のHPと2ch以外に発表の場がないからな

424 ：１３２人目の素数さん：2006/03/28(火) 20:34:41

>>420
ヤマジンは自分でスレを立てることはしない。
スレを立てないのはヤマジンをからかう場がなくなるだけ。
何で、そんなことに力をいれているのか、意味不明。

425 ：１３２人目の素数さん：2006/03/28(火) 20:50:08

もう病人は放置でいいじゃん
放置しておいたほうが病気も良くなるかもしれないし

426 ：１３２人目の素数さん：2006/03/31(金) 12:37:12

解けるNP問題って細かいP問題の集合じゃないか？

427 ：１３２人目の素数さん：2006/04/09(日) 01:04:24

428 ：428：2006/04/09(日) 18:12:29

4*2=8

429 ：１３２人目の素数さん：2006/04/13(木) 17:45:18

P=NPが証明できました

430 ：１３２人目の素数さん：2006/04/13(木) 18:26:08

ｸﾞｯｼﾞｮﾌﾞ

431 ：１３２人目の素数さん：2006/04/13(木) 18:59:40

NP問題は指数時間で解くことができます
指数関数はテーラー展開により多項式になります
ゆえにNP問題は多項式時間で解くことができます
よってP=NPです

432 ：１３２人目の素数さん：2006/04/13(木) 19:54:25

>>431
それって、多項式時間の多項式の定義を無限級数に拡張するってこと?

433 ：１３２人目の素数さん：2006/04/13(木) 21:01:59

>>431
あと、現状 EXP=NEXP もわかってないから、
テーラ展開で多項式とか言う定義だと NP 自体もでっかくなるから、
P だけ追い付くって話じゃないな。

434 ：１３２人目の素数さん：2006/04/13(木) 22:48:38

真面目に返されてしまいました。ﾃﾍｯ

435 ：１３２人目の素数さん：2006/04/15(土) 12:05:25

age

436 ：１３２人目の素数さん：2006/04/16(日) 01:25:26

437 ：１３２人目の素数さん：2006/04/16(日) 09:03:30

真にランダムなデータは生成できないという話だったが、
ＮＰ完全問題に大してランダムでない入力にたいしてだけ
多項式時間で解けるアルゴリズムが発見されたら、
人間が作れる問題に大しては多項式で解けるって事だから、
実用的にはＮＰ問題は解けたってことになるのかな。

438 ：１３２人目の素数さん：2006/04/16(日) 09:43:54

訂正
大して→対して

439 ：１３２人目の素数さん：2006/04/16(日) 18:13:11

NP∩coｰNP問題の具体例についてですが、
英語版Wikipediaによると
ある自然数Nについて、M以下の因数が
存在するかという問題(因数分解)が
NP∩coｰNPに属するそうです。

440 ：１３２人目の素数さん：2006/04/18(火) 19:42:50

>>437
丸２日も放置されるとは、やるな。
奴も万能ではないということか。

441 ：１３２人目の素数さん：2006/04/18(火) 21:26:07

>>437
一応 Complexty Core とか調べてくれ。
あと、 P-immune Set とか。

442 ：１３２人目の素数さん：2006/04/24(月) 10:07:16

ppn

443 ：１３２人目の素数さん：2006/05/07(日) 13:26:02

素人が口挟むことじゃないかもしれないが
ちっとNP問題を調べてて思ったんだが
先に解を与えられてそこから式を導き出すのは無理とか言うのは駄目なの？
いわゆる1+1が分かれば解は求まるが解の2しか分からなければ
式というのは小数点を含めればいくらでも出てくると。
巡回セールスマン、ナップサック、ハミルトンとか見て思った戯言でした。
一応俺はP≠NPだと思う。だけどP=NPが分かれば素敵だろうね。

444 ：１３２人目の素数さん：2006/05/07(日) 18:50:20

できたと思ったら証明を書いてみよう。
私は自分自身すらできたと思っても、
証明を書き上げるまで信用してない。
書いているうちに駄目だったと言うことは何度もある。

445 ：443：2006/05/07(日) 22:40:54

数学専攻では無く理数系ではあるが全くの専門外で
とりあえず証明の書き方すら知らない人間なんで。
このNP問題では当てはまらないだろとかこの場を借りて
意見求めたかったのだが、悪いけどちっとageさせてもらいます

446 ：１３２人目の素数さん：2006/05/08(月) 01:14:39

勇者よ
マターリと神の裁きを待て

447 ：１３２人目の素数さん：2006/05/08(月) 02:08:45

例えば SAT だったら、 yes か no の解が容易に求まれば、
アサイメントを一つずつ固定しては解を求めることを繰り返すことで、
実際の解を計算木の中からバイナリサーチできる。
この方法はナップザックとかなら簡単にできるはず。他の問題も考えてみて。
より詳しく知りたいなら P-selective とか Self-Reducibility とか調べてみて。

あと、解の唯一性に興味があるなら、UPというクラスを調べてみて。

448 ：１３２人目の素数さん：2006/05/08(月) 02:59:34

>>445
正負判別なんて符号桁を見るだけで判別できるが
正負判別も解に対する式が無数に存在するぞ

449 ：１３２人目の素数さん：2006/05/12(金) 20:52:19

ナップザック問題で満足度と大きさの割合を求めて良いほうから選ぶ方法って、アルゴリズムに名前あるんですか？

450 ：１３２人目の素数さん：2006/05/13(土) 08:59:23

age

451 ：１３２人目の素数さん：2006/05/13(土) 22:26:08

452 ：１３２人目の素数さん：2006/05/15(月) 09:00:29

＞４４９
greedy

453 ：１３２人目の素数さん：2006/05/16(火) 21:50:27

NP完全問題が解けるとしたらやっぱりSATかな。

454 ：１３２人目の素数さん：2006/05/17(水) 12:23:48

age

455 ：揚げ足取り：2006/05/17(水) 14:22:13

>>453
さんざん既出だけど、任意のNP完全問題は指数時間で解ける。

つか、解けない問題はEXPにも入らないだろ…

456 ：１３２人目の素数さん：2006/05/17(水) 19:13:07

いやもちろん多項式時間というつもりだったのだが。
まあ、NP完全問題が一つ多項式時間で解けてしまえば、どのNP完全問題も
多項式時間でとけるのはわかっているが、数学的に扱いやすいのはSATなのかなと。

457 ：１３２人目の素数さん：2006/05/17(水) 20:02:13

ランダムグラフのハミルトンサーキットは大抵 yes だ。

458 ：１３２人目の素数さん：2006/05/19(金) 23:26:39

ここらへんでcoNPについて語って見ないか。

459 ：１３２人目の素数さん：2006/05/26(金) 14:40:20

814

460 ：１３２人目の素数さん：2006/06/16(金) 01:18:46

200

461 ：１３２人目の素数さん：2006/06/17(土) 01:05:44

最近NP困難問題を指数時間でもいいからできるだけ少ない計算量
で解こうっていうアプローチが盛んみたいだね．例えば3SATとかは
1<c<2 となる定数 c に対して c^n 時間のアルゴリズムがあるみたい．
でも逆に単純なアルゴリズムに 2^n 時間よりも多くかかるNP完全問題
ってあるんだろうか？

462 ：１３２人目の素数さん：2006/06/17(土) 01:08:53

SATがO(n 2^n)ではなくO(2^n)で解けるアルゴリズムが見つかったのは結構最近だったと思ったが

463 ：１３２人目の素数さん：2006/06/17(土) 01:11:14

もう一つ素朴な疑問．

1990年代初頭からNP困難問題に対する近似不可能性の結果って
あるよね．NP!=Pを仮定するとある種のNP困難問題の近似度がこれ
以上下がりませんよーってやつ．

で，最近MCMC法とか流行ってて#P完全な問題の解の近似が
多く議論されてたりするわけだが，そういう問題に対する近似度の
下限って議論できたりするんだろうか？

464 ：461=463：2006/06/17(土) 01:14:40

>>461
ごめんごめん，言葉足らずでした．多項式時間の部分は無視して，です．
d>2 に対して d^n 時間かかる，って意味です．

465 ：１３２人目の素数さん：2006/06/17(土) 19:34:08

あげ

466 ：１３２人目の素数さん：2006/06/24(土) 20:37:37

近似解で我慢すれば、多項式時間に落ちるというものがあったよね。

467 ：１３２人目の素数さん：2006/06/25(日) 01:18:19

最大クリーク問題に対する多項式定数倍近似アルゴリズムが存在する→P=NPがいえる

468 ：１３２人目の素数さん：2006/06/25(日) 15:21:11

任意のｎ次の正方行列Aが”予め”与えられているときに、
任意のｎ次ベクトルｘを与えて、ｙ＝Axを計算させるとする。
その計算量がO(n^2)より指数が下がらないことは証明されたの？

注：Aは予め与えられているので、幾らでも計算量を使って
予め何かを計算しておいてそれを利用して突然与えられたｘに
対してそれに対応するｙを求めても良いことに注意する。

469 ：１３２人目の素数さん：2006/06/26(月) 00:15:07

>>468
それって今まで下限が全然知られてないの？とても面白そうだね．
できれば関連研究の情報教えてもらえるとうれしいんだけども

470 ：１３２人目の素数さん：2006/06/29(木) 15:12:32

入力サイズがあらかじめ決まってるんだから回路計算量の話だろ
解くだけなら多項式時間で解けるぞ

471 ：１３２人目の素数さん：2006/07/01(土) 16:16:03

行列Aがスパースで一行あたりO(1)個しか非零要素がなければ、Axの計算はO(N)だろ。

472 ：１３２人目の素数さん：2006/07/02(日) 15:57:36

オーダーって普通最悪のケースを考えるんじゃ？

473 ：１３２人目の素数さん：2006/07/03(月) 21:10:31

>>472
もちろん。

>>471
その論で行くなら、sparse なんて中途半端なこと言わずに、
零行列でいいじゃないかｗ

474 ：１３２人目の素数さん：2006/07/03(月) 22:00:30

定数解の場合O(0)でいいの？

475 ：１３２人目の素数さん：2006/07/04(火) 19:35:18

普通はO(1)って書くんじゃないかな

476 ：１３２人目の素数さん：2006/07/23(日) 17:02:30

三年四時間。

477 ：１３２人目の素数さん：2006/07/28(金) 01:50:41

age

478 ：１３２人目の素数さん：2006/07/28(金) 02:29:06

数独がNP完全ってどうやって示すの？

479 ：１３２人目の素数さん：2006/07/28(金) 17:51:29

自明

480 ：１３２人目の素数さん：2006/07/28(金) 18:46:05

数独って多項式時間で解けそうな雰囲気がするけど。
ＮＰ完全ってマジで証明された訳？

481 ：１３２人目の素数さん：2006/07/28(金) 23:14:09

>>480
日経サイエンスの今月号の記事で扱ってた。立ち読みだけど、確かそう書いてあった。

482 ：１３２人目の素数さん：2006/07/28(金) 23:16:05

>>481
まじか。
あんなの消去法でらくらく解けるのかと思ってたがＮＰ完全とは。
恐るべし。

483 ：１３２人目の素数さん：2006/07/28(金) 23:38:18

>480-482
http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf
ASP完全であることを示して, NP完全性を言うんだとさ.

484 ：１３２人目の素数さん：2006/07/28(金) 23:45:46

東大の院生が証明したんだってよ。まさかkingじゃないよなw

485 ：１３２人目の素数さん：2006/08/30(水) 16:22:44

501

486 ：１３２人目の素数さん：2006/09/08(金) 21:01:54

http://arxiv.org/ftp/cs/papers/0609/0609005.pdf
こういうトンデモ論文っていつも出てくるの？

487 ：１３２人目の素数さん：2006/09/09(土) 01:24:27

P=NPなの？

488 ：１３２人目の素数さん：2006/09/09(土) 23:35:48

４８６の餓鬼よ
山口人生様の消滅が最終解決。
こういう発表レベルの結論では話にならない。
いいか、計算量理論は理論としてオカシイの！

489 ：１３２人目の素数さん：2006/09/10(日) 00:07:00

>>488
詳しく

490 ：１３２人目の素数さん：2006/09/10(日) 13:55:08

数独の問題の長さって固定されているから、どうやってもNP完全にはならないと思うんだけれど、これは勉強不足？
（NPなのは明らかなんだけれど）

491 ：１３２人目の素数さん：2006/09/10(日) 18:25:42

>>490
ヒント：将棋・囲碁

492 ：１３２人目の素数さん：2006/09/10(日) 19:37:35

>490
http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf (>483)
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

一般化数独がNP-hardなことしか言ってない. 9*9だと流石に解けるよ.

493 ：１３２人目の素数さん：2006/09/11(月) 20:07:30

４８９よ
山口人生様のサイトの記事（新着情報シリーズ）を読め。
htttp://www.int2.info

494 ：１３２人目の素数さん：2006/09/14(木) 22:48:20

囲碁ってPSPACE完全でいいの？

495 ：１３２人目の素数さん：2006/09/18(月) 17:31:25

物理学的にP≠NPを証明するって研究は存在しないの？
量子の振る舞いがどうだこうだでエントロピーが増大してどうのこうので…
みたいな感じで。

496 ：１３２人目の素数さん：2006/09/18(月) 19:11:21

それならどうだこうだで数学的にやれそう。
がんばれ。

497 ：１３２人目の素数さん：2006/09/23(土) 23:00:46

test

498 ：１３２人目の素数さん：2006/10/03(火) 01:26:52

905

499 ：１３２人目の素数さん：2006/10/03(火) 19:42:48

またヤマジンスレ落ちている
なんでやのん

500 ：１３２人目の素数さん：2006/10/05(木) 01:59:20

>>499
見せ物としての商品価値（もちろん彼にはそれ以外の価値はないのだけれど）すら
なくなってきたから。

501 ：１３２人目の素数さん：2006/10/07(土) 23:34:28

フフン
やっと最終解決したことが認知できたから。

502 ：１３２人目の素数さん：2006/10/07(土) 23:35:26

ここで馬鹿餓鬼が山口人生様の格を下げることを何か言う度に、日本の格が下がる。
連中は、それでいいと言ってる。
これが日本の餓鬼の正体だ。
遠慮なく収入を下げてやれ。
こういう連中が一人前の気分で生きていると、人類の迷惑だ。

503 ：１３２人目の素数さん：2006/10/07(土) 23:38:18

ここは山口人生様の消滅解決法が理解できない数猿の群れ。

504 ：１３２人目の素数さん：2006/10/07(土) 23:39:40

ここで山口人生様の悪口を言う餓鬼集団が日本の労働者の暮らしを傾けている。
その結果、ここの電波餓鬼集団の暮らしも、ますます苦しくなる。
それを見つつ、笑いながら小銭儲けをすることが管理人ヒロユキの目的。
だから、いつまでも、悪口を止めない。

505 ：１３２人目の素数さん：2006/10/08(日) 00:06:07

あー、本格的にこっち来ちまったか。
誰かヤマジン隔離スレ立ててきて。

506 ：１３２人目の素数さん：2006/10/08(日) 18:43:38

ニセモンじゃねえの?
本物だとしても正直飽きられてるので新スレも必要ないだろ
ほうっておけば?

507 ：１３２人目の素数さん：2006/10/11(水) 10:39:57

プロブレム＝ノープロブレム問題
それは解決できんがな('A`)

508 ：１３２人目の素数さん：2006/10/13(金) 05:32:15

なんでヤマジンのスレ落ちたんだ？早く立てろ！

509 ：１３２人目の素数さん：2006/10/14(土) 14:59:20

510 ：山口人生：2006/10/14(土) 17:37:37

俺は英雄だー　英雄なんだーー！！

511 ：１３２人目の素数さん：2006/10/14(土) 17:50:40

ていうかヤマジン、そろそろ他の問題に取り組んでくれw

512 ：１３２人目の素数さん：2006/10/14(土) 19:20:19

このスレはヤマジンのスレじゃないのでヤマジンの話題は禁止。本人の書込みは無視しろ

513 ：１３２人目の素数さん：2006/10/14(土) 20:08:59

　　　　　ﾘ,;;;;;;:: ;;;;;:: ;;;;; ::;;;;;; ＼　　　　　　人从
　　　　　(彡ﾉり／ﾘﾉ" ﾐ;;;;;;,,,.. ゝ　　　　　）あ（
　　　　　);;; ヾ､;;;;...__,,　　）;;;;;;;; ヾ　　　　）お（
　　　　　i:::) ` ;;ー--､`　〈;;;;;;;::;;; i　　　）お（
　　　 i　i::/ 　 ^:::::::..　i　 ,ll/ﾆi ;; l　　） /　（
　　　 i　l ヾヽ''　　　　ﾟ　　 )）ﾉ;; /　）っ　（
　　i　|　 | iにﾆ`i,　　　　 (_／i;;; |　　） !!　（
　　|　|　 ! ｀ｰ‐'"　　　／　　ゞ:l　　つ (⌒
　　i　l|　 ! "￣　,,,. ／,;　　　ﾐi　　　　　　|l
　　|　|i　ヾ二--;‐'　,;;　,;　　　ﾐ　||i　il　　 i|
　　|　ll　＿|彡"　 ,'　;　／'￣＾￣''''＼　　||
　　l ,..-'"　〈　　　 ;　／　　　　　　　　ヽ
　／　､,　＼)　　,,.-/　　　　　　　　　　　`i
　　　　 `　　ﾐｰ,;;'　,l　　　　　　　　　　　　 l
　　　　/　　 ;; /　 .|　　　　　　　　　　　　　|

514 ：１３２人目の素数さん：2006/10/14(土) 20:29:58

それはヤマジュンだ

515 ：１３２人目の素数さん：2006/11/02(木) 08:02:35

別の掲示板でも質問したのでちょっと失礼かとも思ったんですが、
まだ返事がないのでこっちでも質問させてください。

X=(x_1,x_2.....x_n：入力ベクトル。与えられている)
Y=(y_1,y_2... y_m：内部状態。外から値を取り出す必要はない。m=n/2+1で少数切り捨て )

f(X,y_1,y_2....y_m) 　｛f(入力、内部状態）｝

このｆは二進数XをＹで割ったあまりの二進数の桁それぞれについてorをとり、それを否定したものだとします。
つまり、YでXを割り切れればfは1となり、あまりが出れば0となります。

また、fは論理式and、or、notのみで作ることができます（のはずです）。

ここで、y_1=1とします。

f(X,1,y_2....y_m) =?

このfの値が1となるようなy_2....y_mがあるかどうかは充足可能性問題、いわゆるSATでしょうか。

「fの値が1となるようなy_2....y_mがある」時にy_1=1とし、そうでないときに０にすれば、
このステップを繰り返すことによって
Xを割り切れる一番大きな数が出てくると思うのですが、、、、

516 ：１３２人目の素数さん：2006/11/02(木) 20:33:08

fが特殊な性質を持つものに限定しているのでSATじゃないです

517 ：１３２人目の素数さん：2006/11/02(木) 23:55:26

P=NP
P/P=N
1=N
解けた。

518 ：１３２人目の素数さん：2006/11/03(金) 00:12:32

>>515
and と or と not だけで作る事ができるブール式は全部 CNF に還元できるんじゃないの？
要するに入力がビット列で、出力が (0,1) である関数は、全部 SAT と言っても
良い様な気がするけど。

519 ：１３２人目の素数さん：2006/11/03(金) 00:45:19

充足可能性問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動: ナビゲーション, 検索

充足可能性問題（じゅうそくかのうせいもんだい、satisfiability problem, SAT）
は、一つの論理積系 (CNF) が与えられたとき、
それに含まれるすべての変数の値を0(偽)あるいは1(真)にうまく定めることによって
全体の値を1(真)にできるか、という問題という。

520 ：１３２人目の素数さん：2006/11/03(金) 08:28:14

あらゆるブール関数は真理値表にしてCNFに直せばSATにできる。長さが2^nになるけど

521 ：515：2006/11/03(金) 14:56:27

ありがとうございます。
で、今度はfで任意のSATを表せるかどうか考えたんですが、そうすると最悪
y_1,y_2... y_m=0 　　つまり0000000000.... （0がｍ個の二進数）から
y_1,y_2....y_m=1 までの全ての数で割り切れる数（全てのyでf=0となる数）Xを
作らなければならなくなりますよね。

これは｛11111111.... （1がm個の二進数）までの全ての素数*m｝桁の数
になっちゃうので、（これは2^mオーダーになるみたいです）
fはNPにはなるけど、NP完全にはなれないと思いますが、どうでしょうか。

522 ：１３２人目の素数さん：2006/11/03(金) 15:10:10

どう考えてもP≠NP

523 ：１３２人目の素数さん：2006/11/03(金) 16:34:07

ＮＰチップを作ればトランスポッドも可能ってばかな評論家気取りが
書いてるじゃないか。。。

524 ：１３２人目の素数さん：2006/11/03(金) 17:25:35

mod 2 での連立方程式ってだけだから、P じゃない？

525 ：１３２人目の素数さん：2006/11/03(金) 21:36:14

>>522
じゃあ証明してくれ

526 ：１３２人目の素数さん：2006/11/04(土) 12:49:09

>>521
>fはNPにはなるけど、NP完全にはなれない
関数が NP だとかなんとかって、意味が分からない。

>>524
overdetermined な mod 2 の連立方程式系の最適化問題は
NP hard です。

527 ：515：2006/11/04(土) 23:08:11

>>526
関数と思うとアレですけど、入力によって論理式が変わる
yes/noの判定問題と考えることも出来ます。

実際にy_1,y_2... y_mに000000...0から111111...1まで
全て入れてみれば答えが分かるのでクラスNPだと思います。
逆に答えを与えられたらYにそれを入れてみれば正しいか分かりますし。

で、少なくとも入力が指数オーダーじゃないと還元出来ないので
その時点で計算時間も指数オーダーになっちゃう・・・と
思ったのですが、よく考えたら計算過程によっては大丈夫そうですね・・・

でも入力が指数オーダーなら現実的には使い物にならない訳で。

雰囲気として、fはNP完全の問題よりは
制約条件があるお陰でちょっと簡単・・・な感じがしたわけです。
どうでしょうか。

528 ：１３２人目の素数さん：2006/11/10(金) 20:01:56

線形時間で解けないと証明された問題はあるの？

529 ：１３２人目の素数さん：2006/11/10(金) 21:31:24

え？大小関係を基にしたソートは下限がnlognだけど？
そういう話じゃなくて？

530 ：１３２人目の素数さん：2006/11/11(土) 01:45:21

それ要素の長さがlognだから入力長はnlogn。つまり入力長の線形時間だろ
一般の問題については線形で解けないと示された問題はないはず

531 ：１３２人目の素数さん：2006/11/11(土) 07:37:19

俺の持ってる本ではP≠EXPTIMEらしい。
EXPTIME完全な問題は線形時間で解けないとおもふ。

532 ：１３２人目の素数さん：2006/11/11(土) 08:54:48

要素の長さをlognとするならソートの計算量もn(logn)^2になりそうな？

533 ：１３２人目の素数さん：2006/11/11(土) 11:47:17

L完全よりも難しいなら線型時間で解けないのは自明だからP=LかP≠Lかが証明されてないという話だろう

534 ：１３２人目の素数さん：2006/11/12(日) 02:06:56

NP完全問題って線形時間で解けないという事すら証明されていないのね・・・

535 ：１３２人目の素数さん：2006/11/12(日) 07:15:58

ttp://qwiki.caltech.edu/wiki/Complexity_Zoo

L: Logarithmic Space

The class of decision problems solvable by a Turing machine restricted to use
an amount of memory logarithmic in the size of the input, n. (The input itself
is not counted as part of the memory.)

P: Polynomial-Time
Important subclasses of P include L, NL, NC, and SC.

536 ：１３２人目の素数さん：2006/11/14(火) 23:59:53

age

537 ：１３２人目の素数さん：2006/11/19(日) 11:26:29

P=NPが証明される前に量子計算機なんかが発明されたから暗号理論は
もうズタボロ。でも量子計算機が実現できる計算量はクラスexpだから
それをこえるような問題を使って暗号を作ればまだ古典暗号と情報理論
でも有効な暗号は作れるのでは？

538 ：１３２人目の素数さん：2006/11/19(日) 11:46:51

N=1だったらP=NPじゃんwwww

539 ：１３２人目の素数さん：2006/11/19(日) 12:31:35

>>537
>量子計算機が実現できる計算量はクラスexpだから
それを証明できればSTOCで発表出来ると思うよ

540 ：１３２人目の素数さん：2006/11/19(日) 13:15:41

Shorのアルゴリズムで実現できる計算量はクラスExpの間違いｗ

541 ：１３２人目の素数さん：2006/11/19(日) 13:25:53

Shorだと線形な量子ビットしか扱わないけど、これが量子キューブみたい
な感じで超並列にされるとどのくらいになるんだろうか？
クラスexp(exp(exp(n)))とかだろうか？

542 ：１３２人目の素数さん：2006/11/19(日) 17:59:01

>540
BQP=EXP? ShorのアルゴリズムでもEXPはいかないぞ

543 ：１３２人目の素数さん：2006/11/19(日) 18:33:54

計算量のクラスの包含関係が一発でわかる本を教えてください！

544 ：１３２人目の素数さん：2006/11/20(月) 08:38:40

>543
http://www.math.ucdavis.edu/~greg/zoology/intro.html

# Active Inclusion Diagram (requires Firefox 1.5 or Opera 9)
# Static Inclusion Diagram
に包含関係を有向グラフにした画像がある

545 ：１３２人目の素数さん：2006/11/20(月) 18:34:02

クラスYACCの包含関係を教えて下さい

546 ：１３２人目の素数さん：2006/11/21(火) 15:34:40

フフン、猿。

547 ：１３２人目の素数さん：2006/11/21(火) 22:03:06

>>544
見てみたがでかすぎｗ。
アホかと思った。

548 ：１３２人目の素数さん：2006/11/22(水) 15:28:48

いい加減で目覚めろ猿。
神＝山口人生様を無視して計算量は勉強できない。

549 ：１３２人目の素数さん：2006/11/24(金) 23:25:43

グラフの同形問題てＢＱＰに入る？

550 ：１３２人目の素数さん：2006/11/26(日) 04:54:26

離散対数と素因数分解問題に基づく暗号は量子計算機の所為で結局１００年も持たないんでしょ？
量子計算機にも対抗できる暗号知ってる？量子暗号以外で。McElieceとかは？

551 ：１３２人目の素数さん：2006/11/27(月) 18:52:22

>>549
入るかどうか今のところ不明．

>>550
McEliece，格子型暗号，NTRU とか．
実用性は別とすると数論ベースじゃなかったらそれなりにある．

552 ：１３２人目の素数さん：2006/11/29(水) 22:18:59

McElieceｲｲ！！
代数幾何符号を転用するというアイデアがあるけどどれも多変数にすることの
利点を生かしきれてない論文ばっかりでつまらない。
ここで考察したいのは一変数のゴッパから多変数にすることでどれだけ
線形符号の一般的復号問題に近づけることができるか？ということである。
すべての線形符号は代数幾何的であるという結果から見て、一本の曲線
から多様な符号が構成できることに注目したい。どのような曲線からも
構成は可能だが、普通は復号が遅くなるだけなので使われない。構成する
基底や因子を帰ることで同じパラメータを持つ本質的に異なる符号が作れる。
二次元シンドロームの解釈が変わるので構成法が明らかでないもしくは組み
合わせ論的に方法が増大するとそれがセキュリティパラメータになってより
一般の問題に近づけることができるかもしれないと思うけど、どうよ？

553 ：１３２人目の素数さん：2006/11/30(木) 03:33:33

>>552
符号理論については素人だが，一般の線型符号復号問題って
NP困難じゃなかったっけ？NP困難性への公開鍵暗号の安全性
帰着はまず無理だと思うが，「一般の線型符号復号問題に近づいた」
って客観的にどうやって示すの？

554 ：１３２人目の素数さん：2006/11/30(木) 06:17:07

すべての線形符号は代数幾何符号である。（結論）
代数幾何符号を使う⇔一変数ゴッパ符号は落とし戸関数である
対偶を取ってみた。

555 ：１３２人目の素数さん：2006/11/30(木) 11:26:41

>>554
すまんが言いたいことが分からん．結局，多変数ゴッパ符号の復号問題から
構成されたある落とし戸関数の逆計算がNP困難である事を証明したいってこと？

556 ：１３２人目の素数さん：2006/11/30(木) 19:37:31

いろんな構成法が存在するのに全部一括りに代数幾何符号って呼べるところに注目。

557 ：１３２人目の素数さん：2006/11/30(木) 19:52:48

Papadimitriouの計算理論の本って如何よ？
ヒント：２つの同じパラメータを持つ代数幾何符号が同一であるための
必要十分条件は何か？

558 ：１３２人目の素数さん：2006/11/30(木) 20:06:40

一般じゃないけど一変数よりはより大きな符号のクラスを解く問題に帰着できそう。

559 ：１３２人目の素数さん：2006/12/02(土) 16:25:30

>>550
ゴールドバッハ予想の肯定証明が成されれば、
量子暗号すら危ういらしい。
つ漫画より。
儂ゃぁ知らんがな(´･ω･`)

560 ：１３２人目の素数さん：2006/12/03(日) 17:52:15

与えられた正規言語を受理するオートマトンの内、
最小の物を求めるのって簡単にできるんだっけ？

561 ：１３２人目の素数さん：2006/12/05(火) 11:34:09

一般のオートマトンの最小化問題はNP-Hardだったような気がする

562 ：１３２人目の素数さん：2006/12/06(水) 11:52:00

ＮＰには入るの？
それとももっと上のクラス？

563 ：１３２人目の素数さん：2006/12/06(水) 14:24:19

>>562
判定問題じゃないからNPには入らんだろ．
「サイズk以下のオートマトンは存在するか？」
と変換すれば明らかにNP．

564 ：１３２人目の素数さん：2006/12/06(水) 20:43:00

明らかなの？
あるオートマトンが与えられた正規言語を表現しているかどうか判定する
必要があると思うけど、漏れにとってはそれが多項式で判定できるか明らかじゃないんですが。

565 ：１３２人目の素数さん：2006/12/07(木) 09:45:00

('A`)っttp://www.sakabe.nuie.nagoya-u.ac.jp/~sakai/lecture/automata/slide9-handout.pdf

等価性判定も最小化も状態の同値性判定の時点で最短反例の長さに計算量が依存する

566 ：１３２人目の素数さん：2006/12/07(木) 21:17:01

論文はどこに提出すればいいの？

567 ：１３２人目の素数さん：2006/12/07(木) 21:17:49

きんｇ

568 ：560：2006/12/07(木) 22:11:05

ある問題に対して入力のサイズｋ以下の問題を解く最小のオートマトンを考えて、
k→∞にしたときのオートマトンのサイズを考察したらなんか面白い結果が出ないかと思ったのですが。
だめかな？

569 ：１３２人目の素数さん：2006/12/07(木) 22:13:28

オートマトン、フライングポーク、ダースビーフ

570 ：１３２人目の素数さん：2006/12/08(金) 14:57:47

^と&しか使わない行列演算って省略できないの？
例えばベクトルv=(m1,m2,m3,m4),
行列A＝((a1,b1,c1,d1)(a2,b2,c2,d2)(a3,b3,c3,d3)(a4,b4,c4,d4))
とする。
v*A1=(m1&a1)^(m2&a2)^(m3&a3)^(m4&a4)=(m1^m2^m3^m4)&(a1^a2^a3^a4)
つまりm=(m1^m2^m3^m4),a=(a1^a2^a3^a4) <=> m&a
ｎ次元ベクトル演算は、ｖにｎ回の排他的論理和を施したものと、
Aの列ベクトルの排他的論理和をあらかじめ計算しておくことで
行列演算がO(n^2)->O(n)になるのでは？

571 ：１３２人目の素数さん：2006/12/08(金) 17:56:47

>>570 その排他的論理和の計算量は？

572 ：１３２人目の素数さん：2006/12/09(土) 17:33:17

微妙

573 ：１３２人目の素数さん：2006/12/10(日) 17:53:04

>>570
(a and b) xor (c and d) = (a xor c) and (b xor d)

という計算をしているように見えるが、これは成立しない。
(a, b, c, d) = (0, 1, 1, 0) が反例。

574 ：１３２人目の素数さん：2006/12/10(日) 18:26:12

米国軍人のマクモニーグル氏の脳みそにおいてP=NPは証明済み。
P=NP=千里眼

エドガーケイシー，ノストラダムスの脳みそもP=NP

575 ：１３２人目の素数さん：2006/12/26(火) 13:40:46

純粋数学の最大の難問のP=NP問題の証明、あるいは反証は不可能です。

576 ：１３２人目の素数さん：2006/12/26(火) 13:42:10

いつそれが証明されたのか教えてください

577 ：１３２人目の素数さん：2006/12/27(水) 14:00:48

527

578 ：１３２人目の素数さん：2006/12/27(水) 19:38:47

ttututututtuttututututtttut潰すわよ

579 ：１３２人目の素数さん：2006/12/28(木) 15:50:02

５７５、５７６の餓鬼
山口人生様が５年前に最終解決していた。
２００６年末の今頃、その事実が判り始めた。

580 ：１３２人目の素数さん：2007/01/07(日) 19:31:34

ttp://homepage3.nifty.com/mogami/diary/d0701.html
この人の日記の1月4日(木)に、

『ある人がweb日記に、 P≠NP問題を「誰かがお金と時間をくれれば2年くらいで証明して見せる」と書いていた』

ってあるんだけど、このある人って誰か分かる人おらん？

581 ：１３２人目の素数さん：2007/01/09(火) 06:27:51

デツァームィニスティック・ポォリィーノォーミャル・プロォーブレッンム

イズ・ナッート

ナン・デツァームィニスティック・ポォリィーノォーミャル・プロォーブレッンム！

582 ：ワトソン：2007/01/19(金) 03:11:42

はじめて書き込みます。
P≠NPの証明を考えたので、検証してもらえないでしょうか？
-----------------------------------------------------
「神託により解が与えられる」を命題ｐとする。
「多項式時間で解ける」を命題ｑとする。
￢ｐ∧ｑ⇒P　　→　　￢P⇒￢（￢ｐ∧ｑ）　　　①
ｐ∧ｑ⇒NP　　→　　￢NP⇒￢（ｐ∧ｑ）　　　　②
背理法を用いる。P＝NPと仮定する。
￢P＝￢NP　　　③
①、②、③から
￢（￢ｐ∧ｑ）＝￢（ｐ∧ｑ）
￢ｐ∧ｑ＝ｐ∧ｑ
￢ｐ＝ｐ
となり、矛盾する。
従って、仮定P＝NPは誤りである。
よって、P≠NP　となる。
（証明終わり）
-----------------------------------------------------
よろしくお願いします。

583 ：１３２人目の素数さん：2007/01/19(金) 03:12:10

証明が存在したとしても、その最小記述文字数が１０００桁の数になるとすれば、
証明が書き下せることはけっして無い。（宇宙の原子数を越えていたりすれば
無理がある。）
これはありえないことではないだろう。
将棋の完全手順、囲碁の完全手順は存在するが、それを事前に
全部書き下すことは特に囲碁の場合はまず出来ないだろう。
それが現実的には出来ないとすれば、具体的な証明が現実的には
無いということと同じことになる。

584 ：１３２人目の素数さん：2007/01/19(金) 03:20:39

>>583
将棋と囲碁ではどちらの完全手順が広いでしょうかね？？？

585 ：１３２人目の素数さん：2007/01/19(金) 03:24:57

確か局面数では囲碁が10桁か100桁か忘れたがそれぐらい桁違いに多い。

586 ：１３２人目の素数さん：2007/01/19(金) 03:29:36

>>584-585
将棋じゃなかったけ？

587 ：１３２人目の素数さん：2007/01/19(金) 04:53:39

囲碁の方が圧倒的に多いよ

588 ：１３２人目の素数さん：2007/01/27(土) 19:54:41

P≠NP問題に有限サイズの証明が存在しない可能性だってあるんだよね。

589 ：１３２人目の素数さん：2007/01/29(月) 22:12:38

ある論理式があってそれが充足可能ならP=NPで充足不能ならP≠NPと
なるようなものが存在しないかな。

590 ：１３２人目の素数さん：2007/01/31(水) 09:46:31

>>589
充足関係は逆だけども
∃x[￢x∈P ∧ x∈NP]
でいいんでないの？後はPとNPの定義を形式的に書き下す．

591 ：１３２人目の素数さん：2007/01/31(水) 18:56:02

>>590
その式はうまくいけばコンピュータで自動検証可能？
だとしたら夢が広がリング。
そんなに甘くは無いかな？

592 ：１３２人目の素数さん：2007/02/01(木) 21:56:57

量子のスピン方向を用いて情報エントロピーと物理エントロピーの変換が可能ということは知っているか？
そこから、P=NPが正しければエントロピー増大の法則が破られることが証明できるので、少なくともこの世界では物理的にP≠NP。
エントロピー増大の法則が間違ってたら、P=NPの可能性が残るし、エントロピー増大の法則は経験則だから、
絶対に正しいか正しくないかと言う証明にはならんが。

593 ：１３２人目の素数さん：2007/02/02(金) 10:50:56

>>592
>そこから、P=NPが正しければエントロピー増大の法則が破られることが証明できるので、
この部分の詳細を教えてもらえませんか？

594 ：１３２人目の素数さん：2007/02/05(月) 18:19:30

447

595 ：１３２人目の素数さん：2007/02/05(月) 18:22:23

去年の４月１２日にゲーデル賞が発表された
受賞者は
Agrawal, Kayal, Saxena

596 ：１３２人目の素数さん：2007/02/08(木) 22:56:15

ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？

597 ：１３２人目の素数さん：2007/02/09(金) 23:35:38

解の数が分かっているならNPは量子コンピュータで多項式時間内に解けますよね？

598 ：１３２人目の素数さん：2007/02/12(月) 14:37:51

クレイ研究所は肯定的・否定的いずれの解決にも賞金を出すと言ってるが、
決定不能についてはどうなんだろうか。

599 ：１３２人目の素数さん：2007/02/13(火) 00:28:56

肯定的解決：証明
否定的解決：反証 or 決定不能性の証明
なのかな、対称性悪いけど。

600 ：１３２人目の素数さん：2007/02/15(木) 20:54:29

ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？

601 ：１３２人目の素数さん：2007/02/15(木) 21:04:11

マクスウェルの魔

602 ：１３２人目の素数さん：2007/02/16(金) 23:21:16

ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか？

603 ：１３２人目の素数さん：2007/02/16(金) 23:24:10