196: 名無しさん@お腹いっぱい。 ↓ 2009/04/18(土) 02:28:05 ID:1hg3Lv7g [Res (2/3)]
223: 名無しさん@お腹いっぱい。 ↓ 2009/04/18(土) 21:12:48 ID:1hg3Lv7g [Res (3/3)]
http://www.google.com/search%3fhl=ja&lr=&ie=UTF-8&oe=UTF-8&num=50&q=%E9%89%84%E3%81%AE%E7%99%BA%E6%98%8E
\_________________________________________________/
○
ο
o
, ー― 、、
/: : : : :/,_: : : : :\
/ /⌒'こ' `ヽ_|: :: : :ヽ
/,/ / ̄^ヽ |: : : : : :}
/ ,ヘ /: : :i: : :`、 /`|: : : : : : |
/// ゝ_ノ: : :/|、 l 丶/: :.|: : : :|: : :|
// /: :|: : : ,-/ /|ヽ.|- 、: : |: : : /|: : |
' |: :.| |: :' /.|/ | \\ 7: : :./-l、:.|
|: : |∧ / _l_ 、_ |: : :/)/∨ >>194こまけえことはいいんだよzzZZ…
|: :!.v Vヘ'=≠ ヽ== //'/|ー,
∨∨ ∧丶, ' _ ルノ|/;;;;;;/
∨ヽ>| ト ̄▽ ̄,-|;;,_>へ|
/;;;;;;;;;、\\://ブ;;;;;;;,;/|
{\、,、、;;;;;;T;;;;;T;;,.、l/;;;/.;;;;|
j;;;;;;;;;;llヘ;(_lミ(.)彡l_)/;;;;;;;;;;;|
|;;;;;;;;;;;;|;;l;;;;;{;;;;;;;};;;;;l;;/;;;;;;;;;;;;;|
P対NP問題(-たい-もんだい、英:P versus NP)ということもある。
理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、
2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。
クラスPとは、決定性チューリング機械において、多項式時間で判定可能な問題のクラスであり、クラスNPは、
Yesとなる証拠(Witnessという)が与えられたとき、多項式時間でWitnessの正当性の判定(これを検証という)が可能な問題のクラスである。
多項式時間で判定可能な問題は、多項式時間で検証可能であるので、P⊆NPであることは明らかであるが、
PがNPの真部分集合であるか否かについては明確ではない。証明はまだ無いが、多くの研究者はP≠NPだと信じている。
そして、このクラスPとクラスNPが等しくないという予想を「P≠NP予想」という。
仮にP=NPであると示された場合、多項式時間で検証可能な問題は全て多項式時間で判定可能であることを意味し、
未だ効率の悪い指数時間アルゴリズムしかない様々な分野の問題に効率的な計算アルゴリズムが与えられる可能性が示される。
しかし、多くの研究者が長年に渡って多項式時間オーダーのアルゴリズムの開発に取り組んでいるにも関わらず、
そのような効率的なアルゴリズムは見つかっていなかったが私、柊つかさがそれを解決した。
\______________________________________________________/
○
ο
o
, ' ` ヽ 、
, ': : : : /: :./: : : : : : : : : : :丶
/: : : : :/: : /: : /7 /|: : : : : : : :`ヽ、
/ー7: : /: : /: :/:/.// |: : : : : 、: : : : :` 、
イ/: : :/-―ー. / / | ト: : : : |: : : :|: : : ヽ
/: : : :/ /: /|: / / | ||: : : : |: : : :j: : : : }
/: : : : :./ // |/ | .| | V`、.|: : : /: : : : |
/: : : : : :j/ィ' ―- | V V ヽ|: : :/ :| : : :|
./:./|: :/ヘ/r≠ニミ | V: :ト: :/: :/: :、/
/:/ |: : :.〈ノ _- 、 V/:./: :/: :/ |
/ |: /〈 . '-`ミヽ V|/: :/: :/: :|
,‐γ^⌒⌒)/` 、 ゝ、__ ,,ヽ>//: :/: :/:j: :| 賞金100万ドル、すき焼きむにゃZzzzz・・・・・
ヽーー_l、/ / / /つ./_>、 ( ) /ル: :/</:. /./
ニし-ノ`‐'  ̄ ̄ ̄` ゙丶、 /: : :.//ノ/:/ノ
ヽ―_‐/_:_:.:/`/ /V
\/ , 丶,∧/
'-ィ ' ヘ、
`‐(_, ' ,ノ
`‐'ヽ、