5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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 :132人目の素数さん: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 :132人目の素数さん:03/07/23 13:27
NP問題の特徴

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

9 :132人目の素数さん:03/07/23 14:02
>>4
探索問題を定義してくれ.決定問題のことかな.
本来 P や NP は決定問題に限らないよ.
>>8
それだとすべての決定問題が NP になっちゃうので正しくない.

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

10 :132人目の素数さん:03/07/23 14:10
>>9
>探索問題を定義してくれ.決定問題のことかな.

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

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

11 :厨輪:03/07/23 14:19
詳細については、早稲田大学の守屋悦朗氏による
以下のページを参照ください。

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

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

12 :132人目の素数さん:03/07/23 14:28
”解”と書くと>>9のような知ったかでもつっこめてしまう。
でも>>9は正しい内容が何かフォローできない。

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

13 :132人目の素数さん:03/07/23 16:06
マジで日本で一番P=NPに近い人って誰?

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

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

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

15 :132人目の素数さん:03/07/23 19:38
夏厨ならば秋にはいなくなる訳だが

16 :132人目の素数さん: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 :132人目の素数さん:03/07/24 12:03
>>12
>理系板の情報科学総合スレッドとかで真面目な話ができると思うよ
確かにふざけてないけど、真面目というには中身が薄いな。

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

21 :132人目の素数さん: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 :132人目の素数さん:03/07/24 14:45
>>21
「NP=co-NPからP=NPはいえない」とはいえていないんじゃないでしょうか?
本当に「いえない」といえるということは not P=NP がいえることですから。

23 :22:03/07/24 14:49
訂正:
本当に「いえない」といえるということは P=NP が証明できないと
いうことを意味するから。 ,,,でした。


24 :132人目の素数さん:03/07/24 15:32
>>22

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

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

26 :132人目の素数さん:03/07/24 16:40
>>20
おっ、基礎論スレの人だ!
なんか書いて書いてー

27 :132人目の素数さん:03/07/24 16:43
>>25
オラクルは関係ないよね。
もしかして君はNP=co-NPならばP=NPだといってるの?
そうなら、そういってるのは君だけだよ。

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

29 :132人目の素数さん:03/07/24 21:05
要するに今のところNP=co-NPからP=NPが導かれることも、
またNP=co-NPからP≠NPが導かれることも証明されていないと
>>21は言いたいのだろう。

30 :132人目の素数さん:03/07/24 21:18
>>28 考えすぎ。
>>29 あんたが正しい。

31 :132人目の素数さん:03/07/25 01:49
多項式クラスと非多項式クラスという以外にも階層に関する議論はあるのですか?
指数関数クラス以外に、それよりももっと計算量の多いクラスとか。
たとえば指数関数を指数に持つ関数とか、指数関数を指数関数回適用した
関数とか、、、、、

32 :厨輪:03/07/25 10:59
>>31
上を見ればキリがありませんよ(w

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

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

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

34 :私を受理してください:03/07/25 23:42
┏━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┳━┓
┃B┃1┃0┃1┃1┃0┃0┃0┃1┃1┃1┃1┃0┃1┃0┃1┃B┃
┗━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┻━┛
       ↑
      ┏━┓
      ┃P┃
      ┗━┛


35 :私を受理してください:03/07/26 00:09
┏━┳━┳━┳━┳━┳━┓
┃B ┃山┃口┃人┃生┃B┃
┗━┻━┻━┻━┻━┻━┛
       ↑
      ┏━━━┓
      ┃P=NP ┃
      ┗━━━┛



36 :132人目の素数さん:03/07/26 01:24
チューリングマシンで、テープが一次元になっていますが、
テープが二次元的に記録が出来ても、そのような二次元チューリング
マシンにできることは一次元のものと同じなのでしょうか?

37 :132人目の素数さん:03/07/26 01:30
面目を保つにはどうしたらよろしいのでしょうか?

38 :132人目の素数さん:03/07/26 06:07
NP完全性は学部で習うけど、現時点でP≠NPに取り組んでる人は日本にいないと思う。
そもそも日本の計算量プロパーってせいぜい10人くらいなんでは?

39 :132人目の素数さん:03/07/26 09:31
>そもそも日本の計算量プロパーってせいぜい10人くらいなんでは?

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

40 :132人目の素数さん:03/07/26 15:17
西野哲朗氏とか戸田誠之助氏とか

41 :132人目の素数さん:03/07/26 15:29
>>40

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

42 :132人目の素数さん:03/07/26 15:45
10人もいないだろうよ

43 :132人目の素数さん:03/07/26 15:48
竹内外史さんも退官後はP=NP問題を一人でシコシコ考えてるって書いてたな

44 :132人目の素数さん:03/07/26 20:46
>>42
でも三人ってことはないんじゃない?
だったらせいぜい五人っていうはずだもの。
少なくとも五人は名前を挙げられるんじゃない?

45 :ぼるじょあ ◆yBEncckFOU :03/08/02 03:23
     ∧_∧  ∧_∧
ピュ.ー (  ・3・) (  ^^ ) <これからも僕たちを応援して下さいね(^^)。
  =〔~∪ ̄ ̄ ̄∪ ̄ ̄〕
  = ◎――――――◎                      山崎渉&ぼるじょあ

46 :132人目の素数さん:03/08/04 17:57
>>38
日本でもいるよ.
例えば京大の岩間先生とか回路計算量の下限の証明に取り組んでいる.

47 :132人目の素数さん:03/08/19 07:02
1

48 :132人目の素数さん:03/08/19 08:06
予想としてはP=/=NPなので
P=/=NP問題では?

49 :132人目の素数さん:03/08/19 08:12
>>48

「きごう」で変換>≠

50 :132人目の素数さん:03/08/19 09:16
>>48
肯定か否定かわからない問題の場合、予想がどちらであっても
肯定命題を問題とするのは別におかしいとは思わないけどね。

51 :132人目の素数さん:03/08/19 23:50

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


52 :132人目の素数さん:03/08/20 12:03
>>51
確かに、ヤマジン自身は大真面目だからな。ただ、ヤマジンが
書き込んだことに真面目に反応するのは遠慮したいね。

53 :神帝:03/08/26 01:02
猿ども、抵抗はそれまでか?

54 :132人目の素数さん:03/09/12 16:15
人生タンのスッドレが消滅。今後どうなるのか?

55 :132人目の素数さん:03/09/12 21:57
>>54
つづいてるよ。

56 :132人目の素数さん:03/09/23 18:52
山口人生様、ついに自己の証明の根幹部が誤りであったと認めました。

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

57 :132人目の素数さん:03/10/04 23:59
この手の難問を解くブレークスルーは、狭い定義に固執せずに、ちょっと広げた(一見するともっと難しい)問題に対してアプローチすることだと思います。
この分野の日本の理論家は優秀ですが、自由な発想という意味では弱いですね。

58 :132人目の素数さん: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 :132人目の素数さん:03/10/10 21:56

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

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

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


60 :権能:03/10/11 23:42
オイオイ、糞塵アホ猿が戯言ほざいているぜ。
まだ恥をかきたいのか?
山口人生様が「P=NP?」問題を解いた。
何か文句あるか?
素人は、黙ってろ。

61 :132人目の素数さん:03/10/15 20:04
神奈川大が数学で公募してるな(笑)

62 :132人目の素数さん:03/10/17 22:09
岩間さんの教科書、なかなかよさげ

63 :132人目の素数さん:03/10/18 20:26
class of P / class of NP |∽| N / R

N ≠ R

∴ P ≠ NP (EOT)

64 :132人目の素数さん:03/10/28 19:28
どなたか、山口人生様の行方をご存じないでしょうか?
23日の第2回公判からこっち、とんとお見かけしないのですが・・・。

65 :132人目の素数さん:03/11/10 07:31
6

66 :132人目の素数さん:03/12/03 17:55
f


67 :132人目の素数さん:03/12/03 18:08
f

68 :132人目の素数さん:03/12/09 23:57
敗訴age

69 :132人目の素数さん:03/12/12 23:39
新課程の高校の数Aに有りそうな問題(センターでは選択問題に移行)

3人から2人を選んでセクースする順列は?
3P2(←P:Play)

3人から2人を選んでセクースする組合せは?
3C2(←C:セクース)

"P"の場合は同一人物同士のセクースにおいて、上と下の立場が逆転する場合も考慮する

70 :132人目の素数さん:03/12/14 18:14
>>69
P=NP に何にも関係ないし
おまけにそれ算数だし

71 :132人目の素数さん:03/12/17 11:21
    |             |
    |             |
    |             |
__ノ              |   _
| |                    |  ノ\__ヽ  
ヽ二二 ヽ -―- 、         |   \ノ(◎)
_____/ /" ̄ヽヽ____|
   /  / _∧_∧ l OKOK。問題無い。
   |  |/( ´_ゝ`) |        \
   ヽi⌒ ̄_/ ̄ ̄ ̄ ̄/゚ 。    \
    \ \./  FMV  / \.      \
      \ソ/____/ \ノ
       \\::::::::::::::::: \\
         \\_::::::::::::_) )
             ヽ-二二-ン

72 :132人目の素数さん: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 :132人目の素数さん:03/12/24 22:02
>>72
素因数分解が P であったって、P=NP ではないだろう?

74 :あげ:03/12/26 18:36
今、人生タンのHP見ようとしたら、消えていたんだけど、
どうなったのか知っている人いる?
裁判の結果は?

75 :132人目の素数さん:03/12/28 21:59
たまにはP≠NPの方向で証明するトンデモも見てみたいな。

76 :132人目の素数さん: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 :甲陽高1 ◆uqmQ5k/uJs :03/12/30 17:53
>>1
P=NPって何それ? 
両辺Pで割ってN=1だろ? 
お前ら・・どんだけ頭糞なんだよ・・・

79 :132人目の素数さん:03/12/30 17:58
P≠NPならアフォにも天才に勝てるチャンスがありまつね

80 :132人目の素数さん:03/12/30 19:09
>>78 いいね。

R∈R = ¬R∈Rって何それ?
両辺R∈Rで割って¬=1だろ?
お前ら・・どんだけ頭糞なんだよ・・・

81 :オーバーテクナナシー:03/12/30 20:42
>>72
マジ?。
実際にP=NPって証明されると、なんか夢が一つ無くなったような気分。


82 :132人目の素数さん:04/01/03 20:52
んなバカな。
P=NP だったら、計算量理論のここ数十年の理論が全部水泡に帰するよ。

83 :132人目の素数さん:04/01/03 21:29
>>82
間違い無いニダ

84 :132人目の素数さん:04/01/04 11:44
万能チューリングマシンよりも強力な計算機の上でも NP≠P が示せれば,
万能チューリングマシンと等価な計算機の上では NP≠P が云える.
そのより強力な計算機の上で万能チューリングマシンをインタープリット
出来さえすればよいからだ.

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

85 :132人目の素数さん:04/01/08 23:31
オイ、76のキチガイ餓鬼
内容も理解できずに、戯言こくな。
パラドックスって知ってるか?
山口人生様が「P=NP?」問題を解いた。

86 :132人目の素数さん:04/01/08 23:36
山口人生様の15番目のスレは何処だ?

87 ::04/01/09 02:08
ここだ↓(w
http://science2.2ch.net/test/read.cgi/math/1072966661/

88 :132人目の素数さん:04/01/10 16:08
山口人生様の結果を無視して、「P=NP?」問題が真面目に語れるはずもない。
ここの書き込みは、全て、戯言。

89 :132人目の素数さん:04/01/10 23:36
山口人生タンの結果を無視せずして「P=NP?」問題が真面目に語れる筈はない。

90 :132人目の素数さん:04/01/16 03:38
「P=NP?」問題を解いたつもりになり切ってしまっているオメデタイ山口人生様(p;

91 :132人目の素数さん:04/01/18 00:37
もしや、既存の体系の中では証明不能な命題なのではないか?
それなら公理にとることも可能だな。

92 :132人目の素数さん: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 :132人目の素数さん:04/01/19 16:48
>>93
以下の語の定義を述べよ。話はそれからだ。

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

95 :132人目の素数さん:04/01/19 22:16
一般に2-tape deterministic Turing machineの動きを
1-tape deterministic Turing machineでシミュレートするには
どうすればいいのですか?

96 :132人目の素数さん:04/01/20 21:48
>>93
>入力サイズMに対してMの多項式時間の解法は確かに存在するのだが

生成せずに存在は示されない。(終)

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

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

98 :132人目の素数さん:04/01/21 03:36
>>97

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

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

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

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


99 :132人目の素数さん:04/01/21 08:05
>>97
P=NPが決定不能になるのは、多項式時間の解法が
「存在していない」場合に限られる。
存在する場合には、それを示せばよい。
しかし存在しない場合に、その証明(証明は
アルゴリズム同様、長さに限度がある。これ
は常識)があるとは限らない。

100 :132人目の素数さん:04/01/21 08:09
>存在しているかもしれなくて

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

101 :132人目の素数さん:04/01/21 22:47
>>99

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

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

103 :132人目の素数さん:04/01/22 11:06
>後の可能性は

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

104 :132人目の素数さん: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 :132人目の素数さん:04/01/22 17:14
>104

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

106 :132人目の素数さん:04/01/23 03:24
>103
P=NPの証明あるいはP!=NP
の証明が数学的にはあったとしても,その記述が物理的に不可能あるいは
現実的に不可能であれば,発見すらできないはずだ.

107 :132人目の素数さん:04/01/25 19:29
>>99
それは強すぎるな。

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

108 :132人目の素数さん:04/01/27 19:01
ある問題がPであるかどうかを一般的に判定するアルゴリズムは存在しない。
ある問題がNPであるかどうかを一般的に判定するアルゴリズムも存在しない。

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

109 :132人目の素数さん:04/01/28 01:10
線形計画法はLPだが、NPであることはすぐに分かる。
ところが、最近になってLPには多項式時間の解法があることが
わかった。つまりLPというNPの問題がPで解けることが示されたのだ。

110 :132人目の素数さん:04/01/28 01:18
>>109
バカバカしすぎてワロタ…_| ̄|○


111 :132人目の素数さん:04/01/28 01:33
それが大事

112 :132人目の素数さん:04/01/28 01:51
>>109
釣りですか('A`)

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

114 :132人目の素数さん:04/01/30 17:33
``代数幾何方面からP vs NPを解決しようとしてる人がいるらしい''
て聞いたことがあるんですけど
一体どんなアプローチなんですかね
詳しい人,教えて!

115 :132人目の素数さん: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 :132人目の素数さん:04/02/03 22:44
>>116
どもありがとう

118 :恒勝:04/02/23 14:58
フフン


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

120 :132人目の素数さん:04/02/23 18:16
>今年に入って、山口人生様の追っかけか。

うむ。P VS NP系のトンデモと言う意味では
完全にヤマジンの追っかけだな。

121 :恒勝:04/02/25 08:56
120のキチガイ餓鬼よ
フフン。
また歴史上、証拠が残ったぞ。
間抜けが。
この時点(2004年2月25日)で、山口人生様が「P=NP?」問題を完全解決したと認知できてないわけだ、日本猿には。

122 :132人目の素数さん:04/02/25 18:13
>この時点(2004年2月25日)で、山口人生様が「P=NP?」問題を完全解決したと認知できてないわけだ、日本猿には。

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

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

124 :132人目の素数さん:04/02/26 03:31
電波キタ─wwヘ√レvv〜(゚∀゚)─wwヘ√レvv〜─ !!


125 :132人目の素数さん:04/03/07 02:04
331

126 :132人目の素数さん:04/04/01 08:13
874

127 :132人目の素数さん:04/04/10 01:52
最近、この問題の進展がさっぱりないな。

128 :132人目の素数さん:04/04/12 09:38
数論からの独立性って、なんのことなの

129 :132人目の素数さん:04/04/26 03:30
705

130 :132人目の素数さん:04/05/05 23:22
853

131 :132人目の素数さん:04/05/20 16:23
748 名前:132人目の素数さん[sage] 投稿日:04/05/20 01:47
ついに完結か

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

757 名前:132人目の素数さん[] 投稿日:04/05/20 14:15
748のキチガイ餓鬼よ
何の関係があるんだ、「P=NP?」問題と?



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

132 :132人目の素数さん:04/05/20 16:24
あ、↑は山口人生ね。

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

134 :132人目の素数さん:04/05/29 21:02
age

135 :132人目の素数さん:04/06/06 08:07
933

136 :132人目の素数さん:04/06/06 23:23
せっかく更新したのにヤマジンスレはもうない・・・
モロ2chを意識した内容だったのに、これでは実に
無意味ですね。


137 :132人目の素数さん:04/06/07 07:02
あるよ。

【リジェクト】ヤマジンの情報脳内大戦17【上等】
http://science3.2ch.net/test/read.cgi/math/1086333865/

138 :132人目の素数さん:04/06/07 08:02
>>137
136ですサンクスコ。
毎回スレタイがいろいろ変わる難しいインターネットです。


139 :132人目の素数さん:04/06/14 07:00
407

140 :132人目の素数さん:04/06/22 09:31
307

141 :132人目の素数さん:04/07/01 18:37
877

142 :132人目の素数さん:04/07/07 01:52
決定不能なのかも知れないなぁ。

143 :132人目の素数さん:04/07/22 02:12
何かうまいモデルのようなものが作れないかな。
それで、モデルとしてN=NPのものと、N≠NPの両方が作れれば、
面白いことになるんだけど。

144 :132人目の素数さん:04/07/27 21:05
どう面白いのか

145 :132人目の素数さん:04/08/06 22:07
312

146 :132人目の素数さん:04/08/13 16:30
266

147 :132人目の素数さん:04/08/21 02:29
866

148 :132人目の素数さん:04/08/21 02:39
>>144
とりあえず、教科書のページが増える。

149 :132人目の素数さん:04/08/27 23:23
437

150 :132人目の素数さん:04/09/04 15:20
268

151 :132人目の素数さん:04/09/05 00:40
素因数分解がPでないことが示せれば、P≠NPが言えるのだろうかな?

152 :132人目の素数さん:04/09/05 00:49
>>151
素因数分解はNP完全じゃないからそれは違う。
そもそも素因数分解はPに入ることが証明されたはず。


153 :132人目の素数さん:04/09/05 02:07
>>152
>そもそも素因数分解はPに入ることが証明されたはず。

素数判定じゃなくて?

154 :132人目の素数さん:04/09/05 02:16
>>153
あ、そうかも。勘違いスマソ。


155 :132人目の素数さん:04/09/06 14:43
素因数分解 in NP なので,素因数分解 not in P ならば
NPに入るけどPに入らない問題があるからNP≠Pが言える.

156 :132人目の素数さん:04/09/06 15:18
「NP完全な問題が1つでもPに入る事が示されればP=NP」ってのと
ごっちゃになってるな。

157 :132人目の素数さん:04/09/06 15:50
>>155
> 素因数分解 in NP なので,素因数分解 not in P ならば
あのー、P\subseteq NP なんですけど。


158 :132人目の素数さん:04/09/06 15:52
>>157
だから何。

159 :132人目の素数さん:04/09/09 16:05
>>157は何が言いたいの。
教えてエ◇イ人。

160 :132人目の素数さん:04/09/09 18:34
>>158 >>159
155 は間違いということでしょ.

161 :132人目の素数さん: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 :132人目の素数さん:04/09/10 22:35:16
>>162
だね。157は言っている内容自体は間違っちゃいないわな。
何を主張しようとしているかを考えれば、勘違いをしているのは
確かだけど。

164 :132人目の素数さん:04/09/12 20:04:10
これが答だよと言われてそれが本当かどうかを検証する手間がPな問題をNP
という。NP問題のどれでもいいからPではないことを示せればP=NPは否定される。

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

165 :132人目の素数さん:04/09/13 00:57:27
  ::::::::::::::::::::         クソスレ神           ::::::::::/ ):::::::::
:::::(\:::::::            ↓  _人           / / ):::::::::::
:::::/\\             ノ⌒ 丿        /  / /ヽ::::::::::::
:::: ヽ \\         _/   ::(        /  / / /::::::::::::::::
:::: ( \ \\      /     :::::::\      l  三 / / ):::::::::::::::
:::::::ヽ ヽ . ミヽヽ     (     :::::::;;;;;;;)    /   二 / /::::::::::::::::::
::::::: ( \ ヽミ ヽヽ    \_―― ̄ ̄::::::::::  /    二 ___/ヽ ...::::::::::::::
::::... /ヽ ヽ ニ ヽヽ  ノ ̄     :::::::::::::: //   ニ _______/   ...:::::::::
:::.   ヽ____  ニ ヽ ( ´Д`  ::::::::::::::;;;;//    ニ ____ノ     .....::::::::::
      ヽ___,  ニ/ ̄――――― ̄ ̄::::::::\ ニ ___ノ +   + ....:::::::::
        ヽニ -‐(        :::::::::::::::::::::::::::::::::≡ __ノ+ ┼ *:::::::::
         ヽ---\__::::::::::::::::::;;;;;;;;;;;;;;;;;;;;;;;;ノ_ +  ┼  .::::::::::
 :::::...     + ┼ +   +    ー-、___~'''''ー-、   :....::::::::::::
  :::::::....     + ┼    *+     +~~'''ヽ ..:...::::::::::::::::::::
   :::::::::::::::::.....    +   * .   ┼  :....:::::::::::::::::
    ::::::::::::::::::::....: + *     +   .....:::::::::::::::::


166 :132人目の素数さん:04/09/16 14:49:05
>>164
> これが答だよと言われてそれが本当かどうかを検証する手間がPな問題をNP
答えが Yes か No の問題で NP でないものもあるよ.

167 :132人目の素数さん:04/09/16 21:38:13
トランジスタさげ

168 :132人目の素数さん:04/09/18 00:34:21
http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/demo/TSP/index.html

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

169 :132人目の素数さん:04/09/18 00:37:13
↑誤差っていうのは最適解からの誤差ね。

170 :132人目の素数さん:04/09/23 10:43:38
711

171 :132人目の素数さん:04/09/23 14:13:43
Cas Stone Cold said so!!!!!!!


172 :132人目の素数さん:04/09/23 14:16:25
>>165
アホウドリ

173 :132人目の素数さん:04/09/28 05:49:11
812

174 :132人目の素数さん:04/10/04 00:16:51
239

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

176 :132人目の素数さん: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 :132人目の素数さん:04/10/19 03:38:13
462

179 :132人目の素数さん:04/10/19 03:49:58
>>177
DL,NLのLはLOGSPACEの略かな。
時間じゃなくて記憶領域の大きさで測った計算量によるクラス。


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

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

181 :132人目の素数さん:04/10/24 09:46:56
711

182 :132人目の素数さん:04/10/30 21:39:19
612

183 :132人目の素数さん:04/11/04 21:47:33
497

184 :132人目の素数さん:04/11/05 00:49:52
参考になります

185 :132人目の素数さん:04/11/09 11:57:36
178

186 :132人目の素数さん:04/11/14 14:54:30
数学の三大未解決難問は
P=NP問題、
リーマンの予想、
ポアンカレの予想
ですね?


187 :132人目の素数さん:04/11/14 14:59:05
P=NPな訳ないだろ
整数計画問題も多項式時間で解けるってのか?

188 :132人目の素数さん:04/11/15 08:51:35
>>186
数学三大難問は
P=NP問題
ホッジの予想
スタンダードの予想だろ?

189 :132人目の素数さん:04/11/21 02:18:32
713

190 :132人目の素数さん:04/11/21 02:50:33
>>180
あまり関係ない。

191 :132人目の素数さん:04/11/27 14:28:26
748

192 :132人目の素数さん:04/11/27 14:33:21
>>188
いい加減にやめれアホ

193 :132人目の素数さん:04/12/04 23:52:24
436

194 :山本エミ子 ◆YH4ME.Qywg :04/12/05 18:21:30
Aは2行2列の行列。
固有値pに対する固有ベクトルの一つをu、固有値qに対する固有ベクトルの一つをvとする。
uとvの内積をu・vと表しAの転置行列をBとすると

(Au)・v=u・(Bv)

であることを証明せよ。

即出だと思いますが

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

よろしくお願します。

195 :132人目の素数さん:04/12/05 18:45:34
>>194
氏ね、荒らし。

196 :132人目の素数さん:04/12/08 02:46:49
大ニュースです。
韓国人数学者がP=NP問題を解いたそうです。

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

197 :132人目の素数さん:04/12/08 04:41:44
>>196
>>72

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

198 :132人目の素数さん:04/12/14 23:07:22
770

199 :132人目の素数さん:04/12/21 23:34:06
724

200 :132人目の素数さん:04/12/23 19:54:23
素数判定じゃなくて?



201 :132人目の素数さん:04/12/28 19:07:12
720

202 :132人目の素数さん:04/12/31 23:32:30
てst

203 :132人目の素数さん:05/01/01 11:30:17
age

204 :132人目の素数さん:05/01/11 20:02:12
The Complexity Zoo
ttp://www.complexityzoo.com/

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

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

206 :132人目の素数さん:05/01/18 10:05:13
それがわかっただけでも数学ってすごいじゃん

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

208 :132人目の素数さん:05/01/19 02:31:26
ところで、ほとんどの専門家がP≠NPと予想しているらしいのだけど、
その根拠って何だろう?極端な話、10乗オーダーでも100乗オーダーでも
多項式時間では絶対に解けない、というのは何だかすごい話だ。

209 :132人目の素数さん:05/01/31 21:57:35
組み合わせの爆発のまえでは多項式時間などへみたいなもんだ。
とても追いつかん。

210 :132人目の素数さん:05/01/31 22:02:26
>>208
だから、予想なんだって。
どれだけやっても誰も解けないからおそらくそうなんだろう、っていう。

211 :132人目の素数さん:05/01/31 22:10:25
俺も大学院のときはco-NP問題を研究してた。
証明システムを提案して鳩の巣原理が多項式サイズで
証明できることを示したもんだ。



212 :132人目の素数さん:05/02/11 23:05:16
P=NP問題勉強するのに良い教科書教えて下さい

213 :132人目の素数さん:05/02/11 23:12:04
  ,j;;;;;j,. ---一、 `  ―--‐、_ l;;;;;;
 {;;;;;;ゝ T辷iフ i    f'辷jァ  !i;;;;; 
  ヾ;;;ハ    ノ       .::!lリ;;r゙  そう言われていた時期も確かにありました
   `Z;i   〈.,_..,.      ノ;;;;;;;;>
   ,;ぇハ、 、_,.ー-、_',.    ,f゙: Y;;f
   ~''戈ヽ   `二´    r'´:::. `!

214 :132人目の素数さん:05/02/11 23:37:37
俺も学部のころはNP≠Pなんて、俺が夏休みつぶしてまじで考えれば
案外解けるんじゃないかっておもってたよ。

215 :132人目の素数さん:05/02/12 13:38:25
セールスマン
セールスマン

216 :132人目の素数さん:05/02/12 23:46:52
sipser でも読んどけ

217 :132人目の素数さん:05/02/13 01:57:04
PCPってどうよ?

218 :132人目の素数さん:05/02/13 02:35:19
P=NPという公理を設けても矛盾がなく、P≠NPという公理を設けても矛盾が
ないというようなことがあれば面白いのに。

219 :132人目の素数さん:05/02/13 17:25:40
>>216
計算理論の基礎のこと?

220 :132人目の素数さん: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 :132人目の素数さん:05/02/19 16:59:55
396

222 :132人目の素数さん:05/02/19 17:06:39
お舞ら出す本が古すぎw
今業界でのはやりは、
Computability and complexity (Jones)

223 :132人目の素数さん:05/02/20 22:06:27
>>218
独立でしたってか

224 :132人目の素数さん:05/02/21 01:15:42
現実的な意味のある問題だからそれはないと思うが

225 :132人目の素数さん:05/02/24 00:51:45
ハッシュテーブルを用いればO(1)で解けます。

Q.E.D.

226 :132人目の素数さん:05/02/24 06:25:08
age

227 :132人目の素数さん:05/03/06 13:53:49
583

228 :132人目の素数さん:05/03/06 14:10:12
>>225
ハッシュ関数の実装によるけんね

229 :132人目の素数さん:05/03/16 23:14:16
899

230 :132人目の素数さん:05/03/16 23:22:34
このスレは後で読むつもりだが、これを解くのは数学者だろうか?

231 :132人目の素数さん:05/03/17 03:31:28
チューリングマシンは一応数学モデルだから

232 :132人目の素数さん:2005/03/29(火) 01:13:45
702

233 :132人目の素数さん:2005/04/08(金) 11:20:56
未解決問題でもリーマン予想とかに比べたら、P≠NP問題は価値が低いと思う

234 :132人目の素数さん:2005/04/08(金) 22:11:53
>>233
もしまんがいち
P=NP
だったなら実社会への影響はすさまじい
(P≠NPだろうと多くが人が考えているので)


235 :132人目の素数さん:2005/04/11(月) 09:21:11
P=NPなら、たんぱく質の構造がアミノ酸の1次配列から簡単に決めれるし、
CPU等の配線も最適なものが簡単に見つけられるし、多分万能メイドロボも実現できるし
もう人類マンセー!な明るい未来が実現できる。

236 :132人目の素数さん:2005/04/22(金) 11:40:03
>>235
じゃあ、素数判定がP問題で、素因数分解もP問題だから公開鍵式暗号は既に崩壊してるんだね!!

237 :132人目の素数さん:2005/04/22(金) 20:08:11
>236
それでもまだNP-hard baseの公開鍵暗号は崩壊せんよな。
実用的では無いが、あるぞ。

238 :132人目の素数さん:2005/04/23(土) 13:38:57
>>237
基本的に暗号を解く問題はNPに入るだろ.だからそういうのもNP=Pなら崩壊するぞ.
秘密鍵をもらって多項式時間で復号できない暗号なんて意味がない.

239 :132人目の素数さん:2005/04/25(月) 20:59:46
age

240 :132人目の素数さん:2005/04/25(月) 21:08:17
NP=Pでも、その方法がわからないと意味ないじゃん。

241 :132人目の素数さん:2005/04/26(火) 02:12:57
山口人生様のスレはここですか?

242 :132人目の素数さん:2005/04/26(火) 15:55:41
>>236
>素因数分解もP問題
いつこんなことが示されたんだ?

243 :132人目の素数さん: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 :132人目の素数さん:2005/05/26(木) 23:02:46
>>245
まさか両辺をPで割ったとか?
Pが0のときどうする。

248 :132人目の素数さん:2005/05/27(金) 01:07:24
P=0ならば、任意のNについてP=NPが成り立つ

249 :132人目の素数さん:2005/05/27(金) 06:58:17
両辺をPで割るのは既出もいいところ。
ちょうど今ヤフ掲示板で同じ事を言ってる
馬鹿がいるし。

250 :245:2005/05/27(金) 09:50:38
>>249
てかこのスレでも外出だし。

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

251 :132人目の素数さん:2005/05/27(金) 19:40:10
>てかこのスレでも外出だし。

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

252 :132人目の素数さん:2005/05/31(火) 22:56:15
何か手掛かりになる成果。失敗した試みとかってどんなものがあるの?


253 :132人目の素数さん:2005/06/01(水) 00:38:36
>>251
「そとだし」って読んでもた。

254 :132人目の素数さん:2005/06/01(水) 00:52:44
チューリングマシンで表現可能なものと不可能なものとを区別するだけだろ?
鍵は、ヒルベルトがぼけていてで、イデアルの先に答えがあることを見抜くことだ。
不完全性定理も同時に解ける。

255 :245:2005/06/01(水) 01:04:27
という夢をみたんだが。

256 :132人目の素数さん:2005/06/26(日) 00:42:16
188

257 :132人目の素数さん:2005/07/16(土) 04:46:01
素因数分解はNP完全だと示されているわけでもないから
そいつがP問題になっても面白くはない。
やはり男のロマンはNP完全の代表格TSP。

258 :132人目の素数さん:2005/07/16(土) 23:52:00
PNP

NPN

259 :132人目の素数さん:2005/07/20(水) 12:22:24
トランジスタかよ

260 :132人目の素数さん:2005/07/21(木) 23:53:15
P型、N型か(w

261 :132人目の素数さん:2005/07/23(土) 05:27:04
age

262 :132人目の素数さん:2005/07/23(土) 13:02:30
二年。


263 :132人目の素数さん:2005/07/24(日) 16:44:14
L=NLが証明されてるって本当ですか?

264 :132人目の素数さん:2005/07/25(月) 10:22:05
>>263
L=SLでないの?

265 :sage:2005/07/28(木) 21:44:56
>>263
グラフのパスを求める問題(NL完全)がLで解けるって聞いたことあるけど。

>>264
SLって何?

266 :132人目の素数さん:2005/07/28(木) 23:30:25
>265
http://www.complexityzoo.com/#sl

267 :132人目の素数さん:2005/07/28(木) 23:37:37
>>266
なんじゃこれは
クラス多過ぎwww

268 :132人目の素数さん:2005/07/29(金) 00:23:19
>>265
残念ながらそれは264がいってるL=SLだ

269 :132人目の素数さん:2005/07/31(日) 01:51:49
質問していいのか分かんないけど… 悩んでるのでお願いします。
「問題AがNP困難である」というとき,その定義から,AはNPに属するとは限りませんよね。
そんな問題って例えばどんなものがあるんですか?

270 :132人目の素数さん:2005/07/31(日) 02:01:17
自己レスですが…
そんな問題が見つかる,ということは,P=NPが証明される,という理解でよいのでしょうか。

271 :132人目の素数さん:2005/08/01(月) 21:31:55
>>269
NP困難でかつ決定不能な問題があります

272 :132人目の素数さん:2005/08/01(月) 23:40:00
269
決定不能ということは… 
「非決定的計算機を用いたとしても多項式時間で解けない」ってことですか?

273 :132人目の素数さん:2005/08/04(木) 07:51:39
age

274 :132人目の素数さん:2005/08/04(木) 20:21:49
>>272
それは初歩の初歩だろ・・・
決定性TMで決定不能な問題は非決定性TMでも決定不能だよ

275 :132人目の素数さん: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 :132人目の素数さん:2005/08/05(金) 09:49:37
>>269はNP困難な問題があるかどうか?という質問だから
SATがNP困難だよって言っているのでは?

278 :269:2005/08/06(土) 01:04:34
いや,>269では,
「NP困難であるがNPではないような問題A」の問題例が知りたかったんです。

279 :132人目の素数さん:2005/08/06(土) 01:16:27
age

280 :132人目の素数さん:2005/08/06(土) 01:52:31
Problems is No-Problems.
どんな困難も問題にはならない。なぜなら僕らはそれを解くから。
どんな問題も解けないということはない。なぜなら人類はそれを乗り越えていくから。

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

281 :132人目の素数さん:2005/08/06(土) 02:13:16
「P=NP」とは「解法」を知ることッ!「公式」を我が物とすることじゃあッ!
P=NPは「数学」の賛歌ッ!!
数学のすばらしさは勇気のすばらしさ!!
いくら強くてもチューリング・マシンは「勇気」を知らん!
ノミと同類よォーッ!!

282 :132人目の素数さん:2005/08/06(土) 23:25:57
ANAL問題

283 :132人目の素数さん:2005/08/07(日) 00:46:34
>>278
計算可能で無い問題を探せば、皆そうだと思います。

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

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


284 :132人目の素数さん:2005/08/07(日) 06:36:32
計算量クラスAとBの区別は、A完全問題がB完全問題に
「多項式時間で」還元可能か否かで決まる、というのが暗黙の前提。

285 :132人目の素数さん:2005/08/10(水) 22:01:19
任意の自然数nに対しn変数3SATをnの多項式時間でとくアルゴリズムが存在する。
これを証明しますた。


286 :132人目の素数さん:2005/08/10(水) 23:19:43
age

287 :132人目の素数さん:2005/08/11(木) 10:28:08
それは既に証明されてるよ

288 :ゲームバカ:2005/08/16(火) 21:11:31
>>269
計算量の入門書でよいので、ちゃんと読んで
NP困難とNPの定義を理解するのがよい。理解すれば、いくらでも見つけられるよ。
(というか、入門書だと例として載っていたりするけど。。)

289 :132人目の素数さん:2005/08/19(金) 08:33:03
age

290 :132人目の素数さん:2005/08/23(火) 06:53:57
ここで質問するのが適切かどうかわかりませんが、
◆ わからない問題はここに書いてね 172 ◆ から誘導されてきました。

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

291 :132人目の素数さん:2005/08/23(火) 10:34:34
290
P≠NPといった強力な仮定を設定しないとむずかしいと思う。何の仮定もなしに、多項式時間を越える下界を示せた問題自体ほとんどない覚えが。

292 :132人目の素数さん:2005/08/23(火) 20:28:14
290
言い忘れ。AがNP完全である気がするのであれば、AがNP完全であることを示すのが労力低。

293 :290:2005/08/24(水) 11:45:27
なるほど。
つまり方法はなくはないかもしれないが、
少なくともこんな質問をしている俺には無理だろうってことはわかりました。
どうもありがとうございました。

294 :132人目の素数さん:2005/08/26(金) 22:52:09
P=co-NPならP=NPといえますか?

295 :132人目の素数さん:2005/08/28(日) 02:35:15
ナトリウムとリン2つずつあっても一酸化炭素ができるわけではない

296 :132人目の素数さん:2005/08/28(日) 04:04:46
おまえツマンネ

297 :132人目の素数さん:2005/08/28(日) 04:15:36
>>294
既出かと思われますが、以下の2式は成立します。
@ P=NP ⇒ NP=co-NP
A NP≠co-NP ⇒ P≠NP
しかし、矢印の逆方向が成立するかどうかは不明です。

298 :132人目の素数さん:2005/08/28(日) 10:08:53
@もAも未解決かと思ったけど。
文献ある?


299 :132人目の素数さん: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
もしも成立すれば、という意味なのはわかってるんだけど。
@もAもそんなに明らかな定理じゃないよね。



302 :132人目の素数さん:2005/08/30(火) 00:14:05
>>301えっ、そうなの?とりあえず文献をあげるけど。
「計算量理論概説」朝倉書店より。
@(144ページ)定理4.12
P=NPならば、多項式時間階層がi=1の段階でつぶれてNP=co-NPとなる。
A(132ページ)より引用
…実際、NP≠co-NPが成り立つとすればP=co-PなのであるからP≠NPが成り立つことになる。

303 :132人目の素数さん: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 :132人目の素数さん:2005/08/30(火) 21:48:15
ヒント:P=co-P

306 :132人目の素数さん:2005/08/30(火) 22:09:37
>>304
とにかくP=NPならば、すべてのNP問題がP問題でもあるということです。
すべてのP問題がNP問題でもある、というのは現時点で当然のことです。

307 :132人目の素数さん:2005/08/30(火) 22:54:32
304:298 08/30(火) 20:47 [sage]

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

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

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

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

308 :132人目の素数さん:2005/08/30(火) 23:14:35
>>304
ようするに、決定性TMの世界でP=NPが成立するかどうかが大問題なわけです。
非決定性TMの世界ではP=NPは自明に成立します。

309 :132人目の素数さん:2005/08/31(水) 09:49:08
>>308
> 決定性TMの世界でP=NPが成立するかどうかが大問題なわけです。
> 非決定性TMの世界ではP=NPは自明に成立します。

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

310 :132人目の素数さん:2005/09/01(木) 19:47:37
こんなの見つけました。
http://arxiv.org/abs/cs.CC/0502030
NP!=Pが証明されたみたいだけどほんとかな?

311 :132人目の素数さん:2005/09/01(木) 21:28:16

Pop = NiPpon


312 :132人目の素数さん:2005/09/01(木) 22:31:53
>>310
誰か検証してくれ。漏れにはわからん。

313 :132人目の素数さん:2005/09/02(金) 00:45:42
>>310
メールアドレスを見た時点でかなり期待薄。

314 :132人目の素数さん: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 :132人目の素数さん:2005/09/02(金) 22:57:45
いつのまに・・・.nl ってことはオランダ人か。しょーがねぇーなー、海面より低い所に棲んでるからそーゆーよくわからないことをくちばしるようになっちゃうのかな(w

316 :132人目の素数さん: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 :132人目の素数さん:2005/09/03(土) 07:58:55
そこはトンデモをヲチして楽しんでるサイトだろ

318 :132人目の素数さん:2005/09/03(土) 11:16:48
そうなのか、すまんな。海面より低いところに棲んでるからって馬鹿にしてスマソ!

319 :132人目の素数さん:2005/09/03(土) 17:55:38
もしかすると量子コンピュータの上ではP=NPかもしれないね。

320 :132人目の素数さん:2005/09/03(土) 18:00:38
>>319
QTM上でP=NPかどうかという問題は今までさんざん研究されてきた未解決問題ですよ


321 :132人目の素数さん:2005/09/04(日) 00:25:36
>>319-320
PとかNPはQTMでは定義されてないので・・・
BQP⊇NP
かどうかは未解決

322 :132人目の素数さん:2005/09/05(月) 22:39:20
ネタも無いようだしみんなでSATでも解かんかね。
http://www.intellektik.informatik.tu-darmstadt.de/SATLIB/benchm.html

323 :132人目の素数さん:2005/09/22(木) 01:14:33
そういや >>104 のLie代数つかって云々って
結局解けてなかったの?


324 :132人目の素数さん:2005/09/23(金) 18:20:32
age

325 :132人目の素数さん:2005/10/08(土) 15:06:53
631

326 :132人目の素数さん:2005/11/01(火) 23:37:42
トートロジーをSATに多項式時間で帰着できるとき
co-NP=NPが成り立つと思うのですが、その逆は成り立つのでしょうか。
つまりco-NP=NPが成り立つならばトートロジーをSATに多項式時間で
帰着させるアルゴリズムが存在するといえますか?


327 :132人目の素数さん:2005/11/02(水) 00:55:54
いえます

328 :132人目の素数さん:2005/11/02(水) 07:58:33
山口人生様が解決済み。
いまさら何を言っているんだ?

329 :132人目の素数さん:2005/11/18(金) 11:00:31
163

330 :132人目の素数さん:2005/12/03(土) 22:45:51
多項式時間で十分高い確率でNP完全問題の解を見つけられるが
解がなかったときは停止しない。というアルゴリズムが
見つかったとき、P=NPであるといえますか?


331 :132人目の素数さん:2005/12/03(土) 23:23:15
それだけだとBPP⊇NPではないでしょうか。
さらにBPP=PがいえればNP=Pだと思います。
BPP=Pだとは強く予想されていますが。

332 :132人目の素数さん:2005/12/05(月) 13:59:19
age

333 :132人目の素数さん:2005/12/05(月) 22:09:12
Complexity Zoo とか見ると絶望的な気分になる

334 :132人目の素数さん:2005/12/23(金) 18:34:50
BPPを計算する計算機は実在するってことでOK?


335 :132人目の素数さん:2005/12/23(金) 19:25:00
>>334
確か疑似乱数を使っても BPP の能力が落ちないという結果があったはずなので、
Okでしょう。
# PP はだめだけど。

336 :132人目の素数さん:2005/12/30(金) 18:39:31
CPUのマルチコア化が進んでいるが、そのうちコアがめちゃめちゃふえて
実質非決定性の計算もできるようにならないかな。

337 :132人目の素数さん:2005/12/31(土) 10:40:39
>336
コアが1000個になったとしても、
その計算能力はコア一つの場合の1000倍以上には
(本質的には)ならないだろうし、
一方で、非決定性の計算は計算量がインスタンスのサイズに対して
指数的に増えていくから絶望的だと思う。

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

338 :132人目の素数さん:2005/12/31(土) 14:34:43
【かっこ悪い】建部崩れ、見参!【情けないw】
http://science4.2ch.net/test/read.cgi/math/1135765594
【夢vs】結果を出せば職はある?w【現実】
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 :132人目の素数さん:2006/01/02(月) 05:14:46
633

340 :132人目の素数さん:2006/01/02(月) 20:50:40
つかぬことをお聞きしますが、擬似乱数、擬似乱数、
っていってますけど真の乱数は計算できないてことですか?


341 :132人目の素数さん:2006/01/02(月) 23:39:14
>>340
定義を調べてごらん。
計算できるなら乱数ではないでしょ。

342 :132人目の素数さん:2006/01/03(火) 12:25:24
乱数が計算できないことって証明されてるの?
乱数列 R(n) について R(n+1)がR(1)...R(n)だけの情報から計算不可能ならいいんじゃない?

343 :132人目の素数さん:2006/01/03(火) 15:22:06
>>340
チャイティンの「知の限界」「数学の限界」あたりを読まれるとよろしいかと・・・

344 :132人目の素数さん:2006/01/03(火) 16:09:31
いくら言っても全然読まない予感

345 :340:2006/01/03(火) 19:17:53
>>343
>>344
ゲーデルの読み物とかチョロッと見てみましたが、
ぜんぜん訳わかりませんでした。
とほほ。こんな私でも何とかなりますかね?


346 :132人目の素数さん:2006/01/03(火) 22:16:56
無理だろ
あきらめろ

347 :132人目の素数さん:2006/01/03(火) 23:30:43
まさに「痴の限界」(w

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

349 :132人目の素数さん:2006/01/08(日) 23:44:59
ttp://math.bbs.thebbs.jp/1123581360/17

バカ発見w

350 :132人目の素数さん:2006/01/10(火) 10:14:30
age

351 :132人目の素数さん:2006/01/16(月) 15:04:33
まだ続いているのか。
山口人生様の仕事も理解できないレベルの猿の戯言。
「P=NP?」問題は山口人生様が解いた。
東大の馬鹿を筆頭に、トンデモと思うのがアホの証拠。


352 :132人目の素数さん:2006/01/16(月) 23:03:47
残念、ここは先生のためのスレではありませんよ。
がんばって探してくださいね(^^)

353 :132人目の素数さん:2006/01/18(水) 12:06:38
それで、マジメに「P=NP?」問題を語っているつもりか?
素人馬鹿の群れ。

354 :132人目の素数さん:2006/01/18(水) 16:12:16
P=NP
両辺をPでわる
1=N
よって
P≠0のときN=1
P=0のときNは任意

と釣ってみる

355 :132人目の素数さん:2006/01/18(水) 17:57:13
>>354
>>78

356 :132人目の素数さん:2006/01/18(水) 18:06:59
マジレスすると
P-NP=0
因数分解して
P(1-N)=0
P=0,1-N=0
よってP=0又はN=1

357 :132人目の素数さん:2006/01/21(土) 15:46:07
P=NP問題に繋がる、最も簡単な問題を教えてください。

358 :132人目の素数さん:2006/01/21(土) 15:53:06
SAT

359 :132人目の素数さん:2006/01/21(土) 16:55:45
NP∩co-NPに属してPに属することが知られていない問題を教えてください。


360 :132人目の素数さん:2006/01/22(日) 01:20:46
>359
マイナーだがSVP_√nとかどうだろう.
格子の次元をnとして近似度√nの最短ベクトル問題.
これの判定版がNPかつcoNP.

361 :132人目の素数さん:2006/01/22(日) 11:24:14
つParity Game

362 :132人目の素数さん:2006/01/23(月) 22:17:58
>>360
>>361
ありがとうございます。
ゆっくり調べてみます。
ところでNP∩co-NP完全問題というのはあるのでしょうか。

363 :132人目の素数さん: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 :132人目の素数さん:2006/02/02(木) 00:52:46
>362
>ところでNP∩co-NP完全問題というのはあるのでしょうか。
http://qwiki.caltech.edu/wiki/Complexity_Zoo#npiconp
には
(NP∩co-NP) Is not believed to contain complete problems.
とあるね。

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

365 :132人目の素数さん:2006/02/02(木) 16:07:15
age

366 :132人目の素数さん:2006/02/05(日) 08:58:21
pnp

367 :132人目の素数さん:2006/02/05(日) 08:59:01
483

368 :132人目の素数さん:2006/02/23(木) 01:02:46
PvsNP問題に対角論法が使えないという奴だけど、あれって
「オラクルが存在するなら対角論法は使えない」というだけじゃないか?
つまり「オラクルは存在しないので対角論法は使えないとはいえない」
ということになると思うんだが・・・

369 :132人目の素数さん:2006/02/23(木) 02:20:31
age

370 :132人目の素数さん:2006/02/23(木) 10:47:51
>>368
もう少しくやしく

371 :132人目の素数さん:2006/02/26(日) 20:59:13
漏れの本にはオラクルは存在すると書いてあるが。

372 :132人目の素数さん:2006/02/26(日) 21:26:24
もしかしてオラクルは存在しないって言ってるのはある計算を
一ステップで実行するようなの計算機が実在しないってこと
をいってる?それは全然的外れのような。



373 :132人目の素数さん:2006/02/26(日) 21:38:35
入力を読み込むのに線形時間はかかるんだから少なくとも線形時間はかかるだろ

374 :132人目の素数さん:2006/02/26(日) 22:08:58
>>373
そんな餌に(ry

375 :132人目の素数さん:2006/02/26(日) 22:27:08
オラクルをTMで作れるならP=NPで確定


376 :132人目の素数さん: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 :132人目の素数さん:2006/02/27(月) 10:09:50
>>377
オラクル使わずに仮に対角線論法でP≠NPが言えたら任意のオラクルA
に対してP^A≠NP^A が言えるから矛盾.

380 :132人目の素数さん: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 :132人目の素数さん:2006/02/27(月) 13:16:10
>>381
「対角線論法で」というのがポイント.

383 :368:2006/02/27(月) 13:40:29
>>382
その違いが分からないです・・・
PとNPがZFCから独立でないならば対角論法をつかってもつかわなくても
P=NPと仮定すると矛盾が生じるのは変わらないと思うんですが・・・

384 :132人目の素数さん:2006/03/01(水) 22:26:02
age

385 :132人目の素数さん:2006/03/03(金) 23:47:26
>>383
詳しく。

386 :132人目の素数さん:2006/03/04(土) 00:11:37
N=1

387 :132人目の素数さん:2006/03/04(土) 08:22:21
P=NP自身が決定不能問題である可能性はないのか?

388 :132人目の素数さん:2006/03/04(土) 15:27:15
>>383
厳密には対角論法が使えないわけじゃない
それにZFC独立は証明されてない

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

389 :132人目の素数さん:2006/03/04(土) 20:41:02
ここらでひとつNP完全問題を解くプログラムをみんなでインプリメントして見ませんか。

390 :132人目の素数さん:2006/03/04(土) 22:37:39
P≠0ならN=1だし、P=0ならNはすべての複素数じゃね?

391 :132人目の素数さん:2006/03/09(木) 17:05:05
>>390
なあ、ちょっと引っ込んでてくれんか。

392 :132人目の素数さん:2006/03/10(金) 01:03:52
>>390
ワンパターンすぎてつまらん。もっとひねれ




















N=1

393 :132人目の素数さん:2006/03/11(土) 00:41:19
意表をついてN≠1

394 :132人目の素数さん:2006/03/14(火) 14:44:23
半導体の世界では、PNPはNPNと並んで非常に重要であります。

395 :132人目の素数さん:2006/03/14(火) 23:34:49
>>394
そう考えりゃP=NPなんてウソじゃん

396 :132人目の素数さん:2006/03/20(月) 21:44:37
ね氏gnik


397 :GiantLeaves ◆6fN.Sojv5w :2006/03/20(月) 21:55:58
talk:>>396 お前に何が分かるというのか?

398 :132人目の素数さん:2006/03/20(月) 22:02:49
典型レスって
・P=NP⇒1=N
・窒素と燐
・半導体(上と同じだが)
の他に何がある?

399 :132人目の素数さん: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 :132人目の素数さん:2006/03/22(水) 18:44:24
ワロタww

402 :132人目の素数さん:2006/03/22(水) 19:31:50
素因数分解をSATに多項式時間帰着させたいんですが、どうすればいいですか?


403 :132人目の素数さん:2006/03/22(水) 21:18:37
2進数表記してからCookの定理に従って記述すればいい

404 :Pなのか、Pでないのか:2006/03/22(水) 22:03:07
>>399は、主語を all of NP と解釈すれば、文法的にも意味的にも
正しい問いかけになる、という事に今更ながら気付いた。

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


405 :132人目の素数さん:2006/03/22(水) 22:16:29
うまいな、と一瞬思ったけど

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

406 :132人目の素数さん:2006/03/26(日) 15:00:34


407 :132人目の素数さん:2006/03/27(月) 15:32:54
NP完全問題を多項式時間で解くアルゴリズムを見つけてしまったんだけどどうすればいいの?
今度3年生になるので研究室に配属される来年まで待ってから教授に見せればいいかな?

408 :132人目の素数さん:2006/03/27(月) 15:50:06
あらゆる類のNP完全問題を多項式時間内に解けるアルゴリズムっていうこと?

409 :132人目の素数さん:2006/03/27(月) 15:51:45
NP完全問題であるハミルトン閉路問題を多項式時間で解けるので
ハミルトン閉路問題に帰着させればすべてのNP完全問題が多項式時間で解けるはずです

410 :132人目の素数さん:2006/03/27(月) 15:52:49
山口人生超教授に見せればいいと思うよ

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

412 :132人目の素数さん:2006/03/27(月) 16:45:21
論文の書式とか投稿の仕方とかが分からないので研究室に配属されるのを待って
卒論にしようかと思います。どうせ再来年には卒論を書く事になるので

ε-δ論法で解いているので nが∃N_0より大きい場合しか使えず実用性は0な解法ですが・・・

413 :132人目の素数さん:2006/03/27(月) 17:13:28


414 :132人目の素数さん:2006/03/27(月) 18:06:52
>>412
行列の積の高速化の話で70いくつかか80いくつかの行数がいるのもあるし、
別に実用性は全然問題ありません。素数判定の多項式時間の判定も結構遅いし。
発表すればきっと誰かが改良してくれる。

でも、関連論文の調査とかやることは多いのでそこから始めるべき。
本当に解けているなら世界中で同じ解法を何人も思い付いていることもあるから、
早く形にすべきだと思う。

415 :132人目の素数さん:2006/03/27(月) 18:47:57
(´∀`)

416 :132人目の素数さん:2006/03/27(月) 18:49:38
>ハミルトン閉路問題に帰着させれば

そんなの何とでもいえる。
本質的にはただハミルトン閉路問題だけを解くアルゴリズムじゃないか?
しかしもしそれができたらNP完全問題⇔ハミルトン閉路問題が証明できる。。。

と素人が言ってみるテスト。

417 :132人目の素数さん:2006/03/27(月) 20:46:09
age

418 :132人目の素数さん:2006/03/27(月) 20:59:41
正n面体上のハミルトニアンクローズドパス問題

419 :132人目の素数さん:2006/03/28(火) 00:23:37
人生痰スレが埋まったため、こちらに迷惑がかかるおそれがありますが
どうかご容赦ください。

420 :132人目の素数さん:2006/03/28(火) 00:54:36
注意!注意!注意!注意!注意!注意!


人生スレは永久廃止になりました。皆さん立てないでください。
もし立ったらそれは本人が立てたという証拠です。


注意!注意!注意!注意!注意!注意!

421 :132人目の素数さん:2006/03/28(火) 01:08:03
予言。

P=NP かつ P≠NPです。
肯定的解決と否定的解決が同時になされます。
2009年ごろ。

422 :132人目の素数さん:2006/03/28(火) 07:40:26
>>419
早速変なの沸いてるじゃねーか。
責任もってとっとと厨収容所立ててこい。

423 :132人目の素数さん:2006/03/28(火) 16:07:41
彼は自分のHPと2ch以外に発表の場がないからな

424 :132人目の素数さん:2006/03/28(火) 20:34:41
>>420
ヤマジンは自分でスレを立てることはしない。
スレを立てないのはヤマジンをからかう場がなくなるだけ。
何で、そんなことに力をいれているのか、意味不明。

425 :132人目の素数さん:2006/03/28(火) 20:50:08
もう病人は放置でいいじゃん
放置しておいたほうが病気も良くなるかもしれないし

426 :132人目の素数さん:2006/03/31(金) 12:37:12
解けるNP問題って細かいP問題の集合じゃないか?

427 :132人目の素数さん:2006/04/09(日) 01:04:24
2

428 :428:2006/04/09(日) 18:12:29
4*2=8


429 :132人目の素数さん:2006/04/13(木) 17:45:18
P=NPが証明できました

430 :132人目の素数さん:2006/04/13(木) 18:26:08
グッジョブ

431 :132人目の素数さん:2006/04/13(木) 18:59:40
NP問題は指数時間で解くことができます
指数関数はテーラー展開により多項式になります
ゆえにNP問題は多項式時間で解くことができます
よってP=NPです

432 :132人目の素数さん:2006/04/13(木) 19:54:25
>>431
それって、多項式時間の多項式の定義を無限級数に拡張するってこと?

433 :132人目の素数さん:2006/04/13(木) 21:01:59
>>431
あと、現状 EXP=NEXP もわかってないから、
テーラ展開で多項式とか言う定義だと NP 自体もでっかくなるから、
P だけ追い付くって話じゃないな。

434 :132人目の素数さん:2006/04/13(木) 22:48:38
真面目に返されてしまいました。テヘッ

435 :132人目の素数さん:2006/04/15(土) 12:05:25
age

436 :132人目の素数さん:2006/04/16(日) 01:25:26


437 :132人目の素数さん:2006/04/16(日) 09:03:30
真にランダムなデータは生成できないという話だったが、
NP完全問題に大してランダムでない入力にたいしてだけ
多項式時間で解けるアルゴリズムが発見されたら、
人間が作れる問題に大しては多項式で解けるって事だから、
実用的にはNP問題は解けたってことになるのかな。

438 :132人目の素数さん:2006/04/16(日) 09:43:54
訂正
大して→対して

439 :132人目の素数さん:2006/04/16(日) 18:13:11
NP∩coーNP問題の具体例についてですが、
英語版Wikipediaによると
ある自然数Nについて、M以下の因数が
存在するかという問題(因数分解)が
NP∩coーNPに属するそうです。

440 :132人目の素数さん:2006/04/18(火) 19:42:50
>>437
丸2日も放置されるとは、やるな。
奴も万能ではないということか。

441 :132人目の素数さん:2006/04/18(火) 21:26:07
>>437
一応 Complexty Core とか調べてくれ。
あと、 P-immune Set とか。

442 :132人目の素数さん:2006/04/24(月) 10:07:16
ppn

443 :132人目の素数さん:2006/05/07(日) 13:26:02
素人が口挟むことじゃないかもしれないが
ちっとNP問題を調べてて思ったんだが
先に解を与えられてそこから式を導き出すのは無理とか言うのは駄目なの?
いわゆる1+1が分かれば解は求まるが解の2しか分からなければ
式というのは小数点を含めればいくらでも出てくると。
巡回セールスマン、ナップサック、ハミルトンとか見て思った戯言でした。
一応俺はP≠NPだと思う。だけどP=NPが分かれば素敵だろうね。

444 :132人目の素数さん:2006/05/07(日) 18:50:20
できたと思ったら証明を書いてみよう。
私は自分自身すらできたと思っても、
証明を書き上げるまで信用してない。
書いているうちに駄目だったと言うことは何度もある。

445 :443:2006/05/07(日) 22:40:54
数学専攻では無く理数系ではあるが全くの専門外で
とりあえず証明の書き方すら知らない人間なんで。
このNP問題では当てはまらないだろとかこの場を借りて
意見求めたかったのだが、悪いけどちっとageさせてもらいます

446 :132人目の素数さん:2006/05/08(月) 01:14:39
勇者よ
マターリと神の裁きを待て

447 :132人目の素数さん:2006/05/08(月) 02:08:45
例えば SAT だったら、 yes か no の解が容易に求まれば、
アサイメントを一つずつ固定しては解を求めることを繰り返すことで、
実際の解を計算木の中からバイナリサーチできる。
この方法はナップザックとかなら簡単にできるはず。他の問題も考えてみて。
より詳しく知りたいなら P-selective とか Self-Reducibility とか調べてみて。

あと、解の唯一性に興味があるなら、UPというクラスを調べてみて。

448 :132人目の素数さん:2006/05/08(月) 02:59:34
>>445
正負判別なんて符号桁を見るだけで判別できるが
正負判別も解に対する式が無数に存在するぞ

449 :132人目の素数さん:2006/05/12(金) 20:52:19
ナップザック問題で満足度と大きさの割合を求めて良いほうから選ぶ方法って、アルゴリズムに名前あるんですか?

450 :132人目の素数さん:2006/05/13(土) 08:59:23
age

451 :132人目の素数さん:2006/05/13(土) 22:26:08


452 :132人目の素数さん:2006/05/15(月) 09:00:29
>449
greedy

453 :132人目の素数さん:2006/05/16(火) 21:50:27
NP完全問題が解けるとしたらやっぱりSATかな。


454 :132人目の素数さん:2006/05/17(水) 12:23:48
age

455 :揚げ足取り:2006/05/17(水) 14:22:13
>>453
さんざん既出だけど、任意のNP完全問題は指数時間で解ける。

つか、解けない問題はEXPにも入らないだろ…


456 :132人目の素数さん:2006/05/17(水) 19:13:07
いやもちろん多項式時間というつもりだったのだが。
まあ、NP完全問題が一つ多項式時間で解けてしまえば、どのNP完全問題も
多項式時間でとけるのはわかっているが、数学的に扱いやすいのはSATなのかなと。


457 :132人目の素数さん:2006/05/17(水) 20:02:13
ランダムグラフのハミルトンサーキットは大抵 yes だ。

458 :132人目の素数さん:2006/05/19(金) 23:26:39
ここらへんでcoNPについて語って見ないか。


459 :132人目の素数さん:2006/05/26(金) 14:40:20
814

460 :132人目の素数さん:2006/06/16(金) 01:18:46
200

461 :132人目の素数さん:2006/06/17(土) 01:05:44
最近NP困難問題を指数時間でもいいからできるだけ少ない計算量
で解こうっていうアプローチが盛んみたいだね.例えば3SATとかは
1<c<2 となる定数 c に対して c^n 時間のアルゴリズムがあるみたい.
でも逆に単純なアルゴリズムに 2^n 時間よりも多くかかるNP完全問題
ってあるんだろうか?

462 :132人目の素数さん:2006/06/17(土) 01:08:53
SATがO(n 2^n)ではなくO(2^n)で解けるアルゴリズムが見つかったのは結構最近だったと思ったが

463 :132人目の素数さん: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 :132人目の素数さん:2006/06/17(土) 19:34:08
あげ

466 :132人目の素数さん:2006/06/24(土) 20:37:37
近似解で我慢すれば、多項式時間に落ちるというものがあったよね。

467 :132人目の素数さん:2006/06/25(日) 01:18:19
最大クリーク問題に対する多項式定数倍近似アルゴリズムが存在する→P=NPがいえる

468 :132人目の素数さん:2006/06/25(日) 15:21:11
任意のn次の正方行列Aが”予め”与えられているときに、
任意のn次ベクトルxを与えて、y=Axを計算させるとする。
その計算量がO(n^2)より指数が下がらないことは証明されたの?

注:Aは予め与えられているので、幾らでも計算量を使って
予め何かを計算しておいてそれを利用して突然与えられたxに
対してそれに対応するyを求めても良いことに注意する。

469 :132人目の素数さん:2006/06/26(月) 00:15:07
>>468
それって今まで下限が全然知られてないの?とても面白そうだね.
できれば関連研究の情報教えてもらえるとうれしいんだけども

470 :132人目の素数さん:2006/06/29(木) 15:12:32
入力サイズがあらかじめ決まってるんだから回路計算量の話だろ
解くだけなら多項式時間で解けるぞ

471 :132人目の素数さん:2006/07/01(土) 16:16:03
行列Aがスパースで一行あたりO(1)個しか非零要素がなければ、Axの計算はO(N)だろ。

472 :132人目の素数さん:2006/07/02(日) 15:57:36
オーダーって普通最悪のケースを考えるんじゃ?

473 :132人目の素数さん:2006/07/03(月) 21:10:31
>>472
もちろん。

>>471
その論で行くなら、sparse なんて中途半端なこと言わずに、
零行列でいいじゃないかw

474 :132人目の素数さん:2006/07/03(月) 22:00:30
定数解の場合O(0)でいいの?

475 :132人目の素数さん:2006/07/04(火) 19:35:18
普通はO(1)って書くんじゃないかな

476 :132人目の素数さん:2006/07/23(日) 17:02:30
三年四時間。


477 :132人目の素数さん:2006/07/28(金) 01:50:41
age

478 :132人目の素数さん:2006/07/28(金) 02:29:06
数独がNP完全ってどうやって示すの?

479 :132人目の素数さん:2006/07/28(金) 17:51:29
自明

480 :132人目の素数さん:2006/07/28(金) 18:46:05
数独って多項式時間で解けそうな雰囲気がするけど。
NP完全ってマジで証明された訳?

481 :132人目の素数さん:2006/07/28(金) 23:14:09
>>480
日経サイエンスの今月号の記事で扱ってた。立ち読みだけど、確かそう書いてあった。

482 :132人目の素数さん:2006/07/28(金) 23:16:05
>>481
まじか。
あんなの消去法でらくらく解けるのかと思ってたがNP完全とは。
恐るべし。

483 :132人目の素数さん:2006/07/28(金) 23:38:18
>480-482
http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf
ASP完全であることを示して, NP完全性を言うんだとさ.

484 :132人目の素数さん:2006/07/28(金) 23:45:46
東大の院生が証明したんだってよ。まさかkingじゃないよなw

485 :132人目の素数さん:2006/08/30(水) 16:22:44
501

486 :132人目の素数さん:2006/09/08(金) 21:01:54
http://arxiv.org/ftp/cs/papers/0609/0609005.pdf
こういうトンデモ論文っていつも出てくるの?

487 :132人目の素数さん:2006/09/09(土) 01:24:27
P=NPなの?

488 :132人目の素数さん:2006/09/09(土) 23:35:48
486の餓鬼よ
山口人生様の消滅が最終解決。
こういう発表レベルの結論では話にならない。
いいか、計算量理論は理論としてオカシイの!

489 :132人目の素数さん:2006/09/10(日) 00:07:00
>>488
詳しく

490 :132人目の素数さん:2006/09/10(日) 13:55:08
数独の問題の長さって固定されているから、どうやってもNP完全にはならないと思うんだけれど、これは勉強不足?
(NPなのは明らかなんだけれど)

491 :132人目の素数さん:2006/09/10(日) 18:25:42
>>490
ヒント:将棋・囲碁

492 :132人目の素数さん: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 :132人目の素数さん:2006/09/11(月) 20:07:30
489よ
山口人生様のサイトの記事(新着情報シリーズ)を読め。
htttp://www.int2.info


494 :132人目の素数さん:2006/09/14(木) 22:48:20
囲碁ってPSPACE完全でいいの?


495 :132人目の素数さん:2006/09/18(月) 17:31:25
物理学的にP≠NPを証明するって研究は存在しないの?
量子の振る舞いがどうだこうだでエントロピーが増大してどうのこうので…
みたいな感じで。

496 :132人目の素数さん:2006/09/18(月) 19:11:21
それならどうだこうだで数学的にやれそう。
がんばれ。

497 :132人目の素数さん:2006/09/23(土) 23:00:46
test

498 :132人目の素数さん:2006/10/03(火) 01:26:52
905

499 :132人目の素数さん:2006/10/03(火) 19:42:48
またヤマジンスレ落ちている
なんでやのん

500 :132人目の素数さん:2006/10/05(木) 01:59:20
>>499
見せ物としての商品価値(もちろん彼にはそれ以外の価値はないのだけれど)すら
なくなってきたから。

501 :132人目の素数さん:2006/10/07(土) 23:34:28
フフン
やっと最終解決したことが認知できたから。

502 :132人目の素数さん:2006/10/07(土) 23:35:26
ここで馬鹿餓鬼が山口人生様の格を下げることを何か言う度に、日本の格が下がる。
連中は、それでいいと言ってる。
これが日本の餓鬼の正体だ。
遠慮なく収入を下げてやれ。
こういう連中が一人前の気分で生きていると、人類の迷惑だ。


503 :132人目の素数さん:2006/10/07(土) 23:38:18
ここは山口人生様の消滅解決法が理解できない数猿の群れ。

504 :132人目の素数さん:2006/10/07(土) 23:39:40
ここで山口人生様の悪口を言う餓鬼集団が日本の労働者の暮らしを傾けている。
その結果、ここの電波餓鬼集団の暮らしも、ますます苦しくなる。
それを見つつ、笑いながら小銭儲けをすることが管理人ヒロユキの目的。
だから、いつまでも、悪口を止めない。


505 :132人目の素数さん:2006/10/08(日) 00:06:07
あー、本格的にこっち来ちまったか。
誰かヤマジン隔離スレ立ててきて。

506 :132人目の素数さん:2006/10/08(日) 18:43:38
ニセモンじゃねえの?
本物だとしても正直飽きられてるので新スレも必要ないだろ
ほうっておけば?

507 :132人目の素数さん:2006/10/11(水) 10:39:57
プロブレム=ノープロブレム問題
それは解決できんがな('A`)

508 :132人目の素数さん:2006/10/13(金) 05:32:15
なんでヤマジンのスレ落ちたんだ?早く立てろ!

509 :132人目の素数さん:2006/10/14(土) 14:59:20
ここで馬鹿餓鬼が山口人生様の格を下げることを何か言う度に、日本の格が下がる。
連中は、それでいいと言ってる。
これが日本の餓鬼の正体だ。
遠慮なく収入を下げてやれ。
こういう連中が一人前の気分で生きていると、人類の迷惑だ。


510 :山口人生:2006/10/14(土) 17:37:37
俺は英雄だー 英雄なんだーー!!

511 :132人目の素数さん:2006/10/14(土) 17:50:40
ていうかヤマジン、そろそろ他の問題に取り組んでくれw

512 :132人目の素数さん:2006/10/14(土) 19:20:19
このスレはヤマジンのスレじゃないのでヤマジンの話題は禁止。本人の書込みは無視しろ

513 :132人目の素数さん: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 :132人目の素数さん:2006/10/14(土) 20:29:58
それはヤマジュンだ

515 :132人目の素数さん: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(入力、内部状態)}

このfは二進数XをYで割ったあまりの二進数の桁それぞれについて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とし、そうでないときに0にすれば、
このステップを繰り返すことによって
Xを割り切れる一番大きな数が出てくると思うのですが、、、、

516 :132人目の素数さん:2006/11/02(木) 20:33:08
fが特殊な性質を持つものに限定しているのでSATじゃないです

517 :132人目の素数さん:2006/11/02(木) 23:55:26
P=NP
P/P=N
1=N
解けた。

518 :132人目の素数さん:2006/11/03(金) 00:12:32
>>515
and と or と not だけで作る事ができるブール式は全部 CNF に還元できるんじゃないの?
要するに入力がビット列で、出力が (0,1) である関数は、全部 SAT と言っても
良い様な気がするけど。

519 :132人目の素数さん:2006/11/03(金) 00:45:19
充足可能性問題
出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: ナビゲーション, 検索

充足可能性問題(じゅうそくかのうせいもんだい、satisfiability problem, SAT)
は、一つの論理積系 (CNF) が与えられたとき、
それに含まれるすべての変数の値を0(偽)あるいは1(真)にうまく定めることによって
全体の値を1(真)にできるか、という問題という。

520 :132人目の素数さん: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がm個の二進数)から
y_1,y_2....y_m=1 までの全ての数で割り切れる数(全てのyでf=0となる数)Xを
作らなければならなくなりますよね。

これは{11111111.... (1がm個の二進数)までの全ての素数*m}桁の数
になっちゃうので、(これは2^mオーダーになるみたいです)
fはNPにはなるけど、NP完全にはなれないと思いますが、どうでしょうか。

522 :132人目の素数さん:2006/11/03(金) 15:10:10
どう考えてもP≠NP

523 :132人目の素数さん:2006/11/03(金) 16:34:07
NPチップを作ればトランスポッドも可能ってばかな評論家気取りが
書いてるじゃないか。。。

524 :132人目の素数さん:2006/11/03(金) 17:25:35
mod 2 での連立方程式ってだけだから、P じゃない?

525 :132人目の素数さん:2006/11/03(金) 21:36:14
>>522
じゃあ証明してくれ

526 :132人目の素数さん: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 :132人目の素数さん:2006/11/10(金) 20:01:56
線形時間で解けないと証明された問題はあるの?

529 :132人目の素数さん:2006/11/10(金) 21:31:24
え?大小関係を基にしたソートは下限がnlognだけど?
そういう話じゃなくて?


530 :132人目の素数さん:2006/11/11(土) 01:45:21
それ要素の長さがlognだから入力長はnlogn。つまり入力長の線形時間だろ
一般の問題については線形で解けないと示された問題はないはず

531 :132人目の素数さん:2006/11/11(土) 07:37:19
俺の持ってる本ではP≠EXPTIMEらしい。
EXPTIME完全な問題は線形時間で解けないとおもふ。



532 :132人目の素数さん:2006/11/11(土) 08:54:48
要素の長さをlognとするならソートの計算量もn(logn)^2になりそうな?


533 :132人目の素数さん:2006/11/11(土) 11:47:17
L完全よりも難しいなら線型時間で解けないのは自明だからP=LかP≠Lかが証明されてないという話だろう

534 :132人目の素数さん:2006/11/12(日) 02:06:56
NP完全問題って線形時間で解けないという事すら証明されていないのね・・・

535 :132人目の素数さん: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 :132人目の素数さん:2006/11/14(火) 23:59:53
age

537 :132人目の素数さん:2006/11/19(日) 11:26:29
P=NPが証明される前に量子計算機なんかが発明されたから暗号理論は
もうズタボロ。でも量子計算機が実現できる計算量はクラスexpだから
それをこえるような問題を使って暗号を作ればまだ古典暗号と情報理論
でも有効な暗号は作れるのでは?

538 :132人目の素数さん:2006/11/19(日) 11:46:51
N=1だったらP=NPじゃんwwww

539 :132人目の素数さん:2006/11/19(日) 12:31:35
>>537
>量子計算機が実現できる計算量はクラスexpだから
それを証明できればSTOCで発表出来ると思うよ

540 :132人目の素数さん:2006/11/19(日) 13:15:41
Shorのアルゴリズムで実現できる計算量はクラスExpの間違いw

541 :132人目の素数さん:2006/11/19(日) 13:25:53
Shorだと線形な量子ビットしか扱わないけど、これが量子キューブみたい
な感じで超並列にされるとどのくらいになるんだろうか?
クラスexp(exp(exp(n)))とかだろうか?

542 :132人目の素数さん:2006/11/19(日) 17:59:01
>540
BQP=EXP? ShorのアルゴリズムでもEXPはいかないぞ

543 :132人目の素数さん:2006/11/19(日) 18:33:54
計算量のクラスの包含関係が一発でわかる本を教えてください!

544 :132人目の素数さん: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 :132人目の素数さん:2006/11/20(月) 18:34:02
クラスYACCの包含関係を教えて下さい

546 :132人目の素数さん:2006/11/21(火) 15:34:40
フフン、猿。

547 :132人目の素数さん:2006/11/21(火) 22:03:06
>>544
見てみたがでかすぎw。
アホかと思った。

548 :132人目の素数さん:2006/11/22(水) 15:28:48
いい加減で目覚めろ猿。
神=山口人生様を無視して計算量は勉強できない。

549 :132人目の素数さん:2006/11/24(金) 23:25:43
グラフの同形問題てBQPに入る?



550 :132人目の素数さん:2006/11/26(日) 04:54:26
離散対数と素因数分解問題に基づく暗号は量子計算機の所為で結局100年も持たないんでしょ?
量子計算機にも対抗できる暗号知ってる?量子暗号以外で。McElieceとかは?

551 :132人目の素数さん:2006/11/27(月) 18:52:22
>>549
入るかどうか今のところ不明.

>>550
McEliece,格子型暗号,NTRU とか.
実用性は別とすると数論ベースじゃなかったらそれなりにある.


552 :132人目の素数さん:2006/11/29(水) 22:18:59
McElieceイイ!!
代数幾何符号を転用するというアイデアがあるけどどれも多変数にすることの
利点を生かしきれてない論文ばっかりでつまらない。
ここで考察したいのは一変数のゴッパから多変数にすることでどれだけ
線形符号の一般的復号問題に近づけることができるか?ということである。
すべての線形符号は代数幾何的であるという結果から見て、一本の曲線
から多様な符号が構成できることに注目したい。どのような曲線からも
構成は可能だが、普通は復号が遅くなるだけなので使われない。構成する
基底や因子を帰ることで同じパラメータを持つ本質的に異なる符号が作れる。
二次元シンドロームの解釈が変わるので構成法が明らかでないもしくは組み
合わせ論的に方法が増大するとそれがセキュリティパラメータになってより
一般の問題に近づけることができるかもしれないと思うけど、どうよ?

553 :132人目の素数さん:2006/11/30(木) 03:33:33
>>552
符号理論については素人だが,一般の線型符号復号問題って
NP困難じゃなかったっけ?NP困難性への公開鍵暗号の安全性
帰着はまず無理だと思うが,「一般の線型符号復号問題に近づいた」
って客観的にどうやって示すの?

554 :132人目の素数さん:2006/11/30(木) 06:17:07
すべての線形符号は代数幾何符号である。(結論)
代数幾何符号を使う⇔一変数ゴッパ符号は落とし戸関数である
対偶を取ってみた。

555 :132人目の素数さん:2006/11/30(木) 11:26:41
>>554
すまんが言いたいことが分からん.結局,多変数ゴッパ符号の復号問題から
構成されたある落とし戸関数の逆計算がNP困難である事を証明したいってこと?

556 :132人目の素数さん:2006/11/30(木) 19:37:31
いろんな構成法が存在するのに全部一括りに代数幾何符号って呼べるところに注目。

557 :132人目の素数さん:2006/11/30(木) 19:52:48
Papadimitriouの計算理論の本って如何よ?
ヒント:2つの同じパラメータを持つ代数幾何符号が同一であるための
必要十分条件は何か?

558 :132人目の素数さん:2006/11/30(木) 20:06:40
一般じゃないけど一変数よりはより大きな符号のクラスを解く問題に帰着できそう。

559 :132人目の素数さん:2006/12/02(土) 16:25:30
>>550
ゴールドバッハ予想の肯定証明が成されれば、
量子暗号すら危ういらしい。
つ漫画より。
儂ゃぁ知らんがな(´・ω・`)

560 :132人目の素数さん:2006/12/03(日) 17:52:15
与えられた正規言語を受理するオートマトンの内、
最小の物を求めるのって簡単にできるんだっけ?



561 :132人目の素数さん:2006/12/05(火) 11:34:09
一般のオートマトンの最小化問題はNP-Hardだったような気がする

562 :132人目の素数さん:2006/12/06(水) 11:52:00
NPには入るの?
それとももっと上のクラス?


563 :132人目の素数さん:2006/12/06(水) 14:24:19
>>562
判定問題じゃないからNPには入らんだろ.
「サイズk以下のオートマトンは存在するか?」
と変換すれば明らかにNP.

564 :132人目の素数さん:2006/12/06(水) 20:43:00
明らかなの?
あるオートマトンが与えられた正規言語を表現しているかどうか判定する
必要があると思うけど、漏れにとってはそれが多項式で判定できるか明らかじゃないんですが。



565 :132人目の素数さん:2006/12/07(木) 09:45:00
('A`)っttp://www.sakabe.nuie.nagoya-u.ac.jp/~sakai/lecture/automata/slide9-handout.pdf

等価性判定も最小化も状態の同値性判定の時点で最短反例の長さに計算量が依存する

566 :132人目の素数さん:2006/12/07(木) 21:17:01
論文はどこに提出すればいいの?

567 :132人目の素数さん:2006/12/07(木) 21:17:49
きんg

568 :560:2006/12/07(木) 22:11:05
ある問題に対して入力のサイズk以下の問題を解く最小のオートマトンを考えて、
k→∞にしたときのオートマトンのサイズを考察したらなんか面白い結果が出ないかと思ったのですが。
だめかな?


569 :132人目の素数さん:2006/12/07(木) 22:13:28
オートマトン、フライングポーク、ダースビーフ

570 :132人目の素数さん: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
n次元ベクトル演算は、vにn回の排他的論理和を施したものと、
Aの列ベクトルの排他的論理和をあらかじめ計算しておくことで
行列演算がO(n^2)->O(n)になるのでは?

571 :132人目の素数さん:2006/12/08(金) 17:56:47
>>570 その排他的論理和の計算量は?

572 :132人目の素数さん:2006/12/09(土) 17:33:17
微妙

573 :132人目の素数さん: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 :132人目の素数さん:2006/12/10(日) 18:26:12
米国軍人のマクモニーグル氏の脳みそにおいてP=NPは証明済み。
P=NP=千里眼

エドガーケイシー,ノストラダムスの脳みそもP=NP

575 :132人目の素数さん:2006/12/26(火) 13:40:46
純粋数学の最大の難問のP=NP問題の証明、あるいは反証は不可能です。

576 :132人目の素数さん:2006/12/26(火) 13:42:10
いつそれが証明されたのか教えてください

577 :132人目の素数さん:2006/12/27(水) 14:00:48
527

578 :132人目の素数さん:2006/12/27(水) 19:38:47
ttututututtuttututututtttut潰すわよ

579 :132人目の素数さん:2006/12/28(木) 15:50:02
575、576の餓鬼
山口人生様が5年前に最終解決していた。
2006年末の今頃、その事実が判り始めた。

580 :132人目の素数さん:2007/01/07(日) 19:31:34
ttp://homepage3.nifty.com/mogami/diary/d0701.html
この人の日記の1月4日(木)に、

『ある人がweb日記に、 P≠NP問題を「誰かがお金と時間をくれれば2年くらいで証明して見せる」と書いていた』

ってあるんだけど、このある人って誰か分かる人おらん?

581 :132人目の素数さん:2007/01/09(火) 06:27:51
デツァームィニスティック・ポォリィーノォーミャル・プロォーブレッンム

イズ・ナッート

ナン・デツァームィニスティック・ポォリィーノォーミャル・プロォーブレッンム!

582 :ワトソン:2007/01/19(金) 03:11:42
はじめて書き込みます。
P≠NPの証明を考えたので、検証してもらえないでしょうか?
-----------------------------------------------------
「神託により解が与えられる」を命題pとする。
「多項式時間で解ける」を命題qとする。
¬p∧q⇒P  →  ¬P⇒¬(¬p∧q)   @
p∧q⇒NP  →  ¬NP⇒¬(p∧q)    A
背理法を用いる。P=NPと仮定する。
¬P=¬NP   B
@、A、Bから
¬(¬p∧q)=¬(p∧q)
¬p∧q=p∧q
¬p=p
となり、矛盾する。
従って、仮定P=NPは誤りである。
よって、P≠NP となる。
(証明終わり)
-----------------------------------------------------
よろしくお願いします。


583 :132人目の素数さん:2007/01/19(金) 03:12:10
証明が存在したとしても、その最小記述文字数が1000桁の数になるとすれば、
証明が書き下せることはけっして無い。(宇宙の原子数を越えていたりすれば
無理がある。)
これはありえないことではないだろう。
将棋の完全手順、囲碁の完全手順は存在するが、それを事前に
全部書き下すことは特に囲碁の場合はまず出来ないだろう。
それが現実的には出来ないとすれば、具体的な証明が現実的には
無いということと同じことになる。

584 :132人目の素数さん:2007/01/19(金) 03:20:39
>>583
将棋と囲碁ではどちらの完全手順が広いでしょうかね???

585 :132人目の素数さん:2007/01/19(金) 03:24:57
確か局面数では囲碁が10桁か100桁か忘れたがそれぐらい桁違いに多い。

586 :132人目の素数さん:2007/01/19(金) 03:29:36
>>584-585
将棋じゃなかったけ?


587 :132人目の素数さん:2007/01/19(金) 04:53:39
囲碁の方が圧倒的に多いよ

588 :132人目の素数さん:2007/01/27(土) 19:54:41
P≠NP問題に有限サイズの証明が存在しない可能性だってあるんだよね。



589 :132人目の素数さん:2007/01/29(月) 22:12:38
ある論理式があってそれが充足可能ならP=NPで充足不能ならP≠NPと
なるようなものが存在しないかな。

590 :132人目の素数さん:2007/01/31(水) 09:46:31
>>589
充足関係は逆だけども
∃x[¬x∈P ∧ x∈NP]
でいいんでないの?後はPとNPの定義を形式的に書き下す.

591 :132人目の素数さん:2007/01/31(水) 18:56:02
>>590
その式はうまくいけばコンピュータで自動検証可能?
だとしたら夢が広がリング。
そんなに甘くは無いかな?

592 :132人目の素数さん:2007/02/01(木) 21:56:57
量子のスピン方向を用いて情報エントロピーと物理エントロピーの変換が可能ということは知っているか?
そこから、P=NPが正しければエントロピー増大の法則が破られることが証明できるので、少なくともこの世界では物理的にP≠NP。
エントロピー増大の法則が間違ってたら、P=NPの可能性が残るし、エントロピー増大の法則は経験則だから、
絶対に正しいか正しくないかと言う証明にはならんが。


593 :132人目の素数さん:2007/02/02(金) 10:50:56
>>592
>そこから、P=NPが正しければエントロピー増大の法則が破られることが証明できるので、
この部分の詳細を教えてもらえませんか?

594 :132人目の素数さん:2007/02/05(月) 18:19:30
447

595 :132人目の素数さん:2007/02/05(月) 18:22:23
去年の4月12日にゲーデル賞が発表された
受賞者は
Agrawal, Kayal, Saxena

596 :132人目の素数さん:2007/02/08(木) 22:56:15
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか?

597 :132人目の素数さん:2007/02/09(金) 23:35:38
解の数が分かっているならNPは量子コンピュータで多項式時間内に解けますよね?

598 :132人目の素数さん:2007/02/12(月) 14:37:51
クレイ研究所は肯定的・否定的いずれの解決にも賞金を出すと言ってるが、
決定不能についてはどうなんだろうか。

599 :132人目の素数さん:2007/02/13(火) 00:28:56
肯定的解決:証明
否定的解決:反証 or 決定不能性の証明
なのかな、対称性悪いけど。

600 :132人目の素数さん:2007/02/15(木) 20:54:29
ユークリッド巡回セールスマン問題を多項式時間で解くことができればP=NPが証明できるのでしょうか?

601 :132人目の素数さん:2007/02/15(木) 21:04:11
マクスウェルの魔

602 :132人目の素数さん: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 :132人目の素数さん:2007/02/16(金) 23:24:10
ユークリッド巡回セールスマン問題を多項式時間で解くことができれば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が証明できるのでしょうか?

604 :132人目の素数さん:2007/02/16(金) 23:24:42
ユークリッド巡回セールスマン問題を多項式時間で解くことができれば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が証明できるのでしょうか?

605 :132人目の素数さん:2007/02/16(金) 23:26:18
ユークリッド巡回セールスマン問題を多項式時間で解くことができれば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が証明できるのでしょうか?

606 :132人目の素数さん:2007/02/17(土) 00:40:43
http://en.wikipedia.org/wiki/Traveling_salesman_problem#Euclidean_TSP

↑ここを参照。
ユークリッドTSP∈NP-hard。
ユークリッドTSP∈P ⇔ P=NP。

607 :132人目の素数さん:2007/02/17(土) 11:51:14
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

608 :132人目の素数さん:2007/02/17(土) 21:26:13
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

609 :132人目の素数さん:2007/02/17(土) 21:26:45
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

610 :132人目の素数さん:2007/02/17(土) 21:27:20
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

611 :132人目の素数さん:2007/02/17(土) 21:27:54
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

612 :132人目の素数さん:2007/02/17(土) 21:28:28
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

613 :132人目の素数さん:2007/02/17(土) 21:29:11
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

614 :132人目の素数さん:2007/02/17(土) 21:29:41
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

615 :132人目の素数さん:2007/02/17(土) 21:30:12
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

616 :132人目の素数さん:2007/02/17(土) 21:30:43
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

617 :132人目の素数さん:2007/02/17(土) 21:31:19
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

618 :132人目の素数さん:2007/02/17(土) 21:31:58
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

619 :132人目の素数さん:2007/02/17(土) 22:06:23
Lin Kernighan って

リン カーニグハンみたいな発音でいいの?

620 :132人目の素数さん:2007/02/17(土) 22:54:39
gはサイレントだろ、常識的に考えて……

621 :132人目の素数さん:2007/02/18(日) 01:03:41
それでは

リン カーニハン

でいいの?

622 :132人目の素数さん:2007/02/18(日) 09:39:44
>>621
荒らすなよクズが。
せっかくの良スレが台無しだろ。

623 :132人目の素数さん:2007/02/18(日) 11:19:55
それでは

リン カーニハン

でいいの?

124 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)