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