P≠NP予想は実は1989年には解かれていた?!教えて偉い人
2部グラフから最大の完全2部グラフを求める方法が1989年には論文で触れられている。この問題はNP完全の筈だけど、P=NPなの?どうなの?
コメントの方の指摘で、読み間違いでKn,mのn+mが最大ではなく、辺n*mが最大のもののようでした。
-
- いいね！0
TANIGUCHI Kousuke
@tinsep19
2部グラフから最大の完全2部グラフさがす方法おもいついて、でもこれNP完全の筈だしって先行事例しらべたら1989年の論文が同じ方法つかっていて、P≠NP予想にはふれられていなかった。
2017-06-05 10:40:23
TANIGUCHI Kousuke
@tinsep19
ja.wikipedia.org/wiki/%E5%AE%8C… … 2部グラフから、辺数m,nが最大となる完全2部部分グラフKm,nを求める問題は、NP完全問題である。 Wikipediaが間違っていなければNP完全の筈
2017-06-05 11:21:43
TANIGUCHI Kousuke
@tinsep19
G=(U∪V,E)の2部グラフに対して、最大マッチング->最小頂点被覆->最大独立集合(IS)の順で調べてGの補グラフG*を考えると、U,VはそれぞれクリークでISはU、Vの一部を含むクリークなので、補2部グラフで最大完全2部グラフを求めているよ。というのが概要。
2017-06-05 10:56:09
TANIGUCHI Kousuke
@tinsep19
1989年の論文 自然言語処理の論文でP.5でふれられている ipsj.ixsq.nii.ac.jp/ej/index.php?a…
2017-06-05 11:05:50
TANIGUCHI Kousuke
@tinsep19
NP完全としらず、多項式で解いてしまった例か、P≠NPじゃないと都合が悪いからみたいな陰謀論か。 1989年ってことは、ミレニアム問題の前だから、P≠NP予想があまり知られていなかったか。なんだろうな。
2017-06-05 11:08:07
TANIGUCHI Kousuke
@tinsep19
Wikipediaの日本語版だとKm,nが最大(m+nが最大)みたいに書いているけど、 英語版だとKi,iとあって、K2,2とかK3,3とかが最大みたいに書いてあるように見える
2017-06-05 14:43:18
TANIGUCHI Kousuke
@tinsep19
2部グラフから辺数m,n が最大となる完全2部部分グラフを求める問題はNP完全って、Km,nのm+nが最大のものを探すの? それともKn,nである最大のnを探すの? よろしくおねがいします。#数学 #競技プログラミング
2017-06-05 15:01:58