P=NPだと夢がある。高温処理済みコースケスマートフォン用の表示で見る高温処理済みコースケ2017-04-07P=NPだと夢がある。極大グラフが1つになるまでは(底を小さくするという意味ではもう少し改善はあるのだろうけど)、たぶん最速だとおもう。あとは補グラフの辺数wをなるべく少なく消しながら、進めばよい。これは一緒に補グラフの最大独立問題をやってるに等しい。少なくとも、NP完全問題が難しいのは、頂点に関するものと辺に関するものを両方一緒にやるからというのが現在の認識。全部辺の問題に還元しながらやっていくのがたぶんよい。下記の資料をみていて、葉最大全域木でなんかインスピレーション湧いた。algorithmで結構高速にできそう。追記2最大クリーク問題である条件下で、多項式時間で計算量一気に短縮できる処理があって、それを常に続けられると多項式時間になるのになぁとおもっている。11:59P=NPだと夢がある。Vacation月別アーカイブはてなブログをはじめよう!tinsep19さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。