P≠NP予想は証明されたのか？

@makotoozawa

P≠NP 予想、証明されるか ? http://slashdot.jp/science/10/08/09/012214.shtml

@makotoozawa

Vinay Deolalikar氏のP is not equal to NPの論文 http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_preliminary.pdf

@makotoozawa

次々と大きな予想が解かれていく。凄い時代だ！

@makotoozawa

空間グラフの論文が本日２本同時に挙がっています。大変活発な分野です。 http://arxiv.org/abs/1008.1095 http://arxiv.org/abs/1008.1085

@makotoozawa

与えられた結び目が自明であるかどうかという問題は、Hass-Lagarias-PippengerによってNPであることが示されている。 http://en.wikipedia.org/wiki/Unknotting_problem

@makotoozawa

クラスPとは、多項式時間で判定可能な問題のクラスであり、クラスNPとは、多項式時間で検証可能な問題のクラスである。 http://bit.ly/axPjq3

@makotoozawa

従って、P（多項式時間で判定可能な問題）⊆NP（多項式時間で検証可能な問題）であるが、現在、P≠NPであることが証明されたと話題になっている。http://bit.ly/b52bk0

@makotoozawa

与えられた結び目が自明であると分かっていたとして、それを多項式時間で検証可能であることがHass-Lagarias-Pippengerによって示されている。http://bit.ly/cnDpcq

@makotoozawa

結び目を解く為のアルゴリズムはいくつか知られているが、Hass-Lagariasは実際に解く為に必要なライデマイスター移動の回数の上限を与えている。 http://bit.ly/amcbET

@makotoozawa

Hass-Lagariasによる結び目を解く為のライデマイスター移動の回数の上限は、ごく最近Henrich-Kauffmanによって劇的に改良されている。 http://bit.ly/bRX3ZD

@makotoozawa

結び目の自明性問題がPでなければ、素数が暗号に使われているのと同様に、結び目も暗号に使うことができる。

@makotoozawa

P≠NP予想について、こちらのブログが分かり易い。http://bit.ly/bjwMzz

@makotoozawa

@sei1tani 現在P≠NP問題が解けたと噂されておりますが、結び目の自明性問題はNPであるがPではないのですよね？

Seiichi Tani @sei1tani

自明性はNPに入るコトが示されていますが、Pに入るかどうかは分かっていません。 RT @makotoozawa: @sei1tani 現在P≠NP問題が解けたと噂されておりますが、結び目の自明性問題はNPであるがPではないのですよね？

Seiichi Tani @sei1tani

Agol が非自明性もNPに入ることを証明したらしいのですが、それが正しいかどうか私は確認していません。 RT @sei1tani: 自明性はNPに入るコトが示されていますが、Pに入るかどうかは分かっていません。 RT @makotoozawa: @sei1tani 現在P≠NP

@makotoozawa

@sei1tani 谷先生、ご回答ありがとうございます。何と、結び目の自明性問題がPでないことが示されていないとは驚きです。

@makotoozawa

@sei1tani 非自明性がNPに入ることは、自明性がNPに入ることから従いそうな気もしますが、それは安直な考えなのですね。

@makotoozawa

正直、P≠NP予想は傍から眺めていただけでしたが、問題解決においてメタレベルの根本的な問題であると認識し始めました。

Seiichi Tani @sei1tani

NPは補問題に関して閉じている(NP=co-NP)かどうか分かってないので、自明性 in NP が直ちに 非自明性 in NP を意味するわけではありません。 RT @sei1tani: Agol が非自明性もNPに入ることを証明したらしいのですが RT @makotoozawa

@makotoozawa

@sei1tani なるほど。やはりそうでしたか。「P=NP⇒NP=co-NP」であることが示されていて、今回、P≠NPが分かった（？）からと言って、NP≠co-NPと帰結はできないのですね。

Seiichi Tani @sei1tani

はい。P は補問題で閉じていますので。RT @makotoozawa: @sei1tani なるほど。やはりそうでしたか。「P=NP⇒NP=co-NP」であることが示されていて、今回、P≠NPが分かった（？）からと言って、NP≠co-NPと帰結はできないのですね。

Seiichi Tani @sei1tani

書かれている通り、P≠NPが証明されても、NP≠co-NPとNP≠co-NPとの両法の可能性があります。RT @makotoozawa: @sei1tani ... 今回、P≠NPが分かった（？）からと言って、NP≠co-NPと帰結はできないのですね。

Seiichi Tani @sei1tani

@makotoozawa NPに属する問題は、直感的には、決定問題の内で多項式長の証拠が与えられるとそれが正しいかどうかを決定性アルゴリズムで多項式時間で判定できると言えます。

Seiichi Tani @sei1tani

@makotoozawa 自明性判定問題ですと、例えば、その結び目が境界となる円盤が証拠となり、その確認は多項式時間で行えます。非自明性な結び目にはそのような円盤が存在しませんが、それを多項式長の証拠で確認出来るか不明。乱暴にいうとNPは存在でco-NPは全称というイメージです。

@makotoozawa

一般化ぷよぷよのNP完全性 http://bit.ly/duzTaa