使い方が違うと思う

これはぼくの推測だが、彼らはこれほどのスピードでウェブが発展するとは当時全く思わなかったんじゃないか。もし未来が見えていたなら、この問題はノード数の加速度的な時間発展が加わるとNP完全くさいぞということに気がついて、まともなコンピュータサイエンティストなら捨て去ったアイデアだっただろう。そういう未来が見えなかったからこそ、こんな困難が待ち受けてるとも知らずにふらりと一歩を踏み出せたんじゃないか。

ともかく、彼らは踏み出した。踏み出してからは、怒濤の日々だ。ウェブは常に発展してきた。それは単なるy=cx的な発展ではなくて、y=cx的な発展だった。それが意味するところは、毎日それまで存在しなかった新しい問題が出現するということだ。

「リンク関係を有向グラフにして, それを0-1隣接行列とみて, 推移確率行列に直してやって, 絶対値が最大の固有値に対応する固有ベクトルを求める」というのがPageRankの作り方→Googleの秘密 - PageRank 徹底解説

この問題はノード数の加速度的な時間発展が加わるとNP完全くさいぞということに気がついてという点が気になった.
行列の次元nが加速度的な増え方をしているのが問題であって, PageRankを求める問題はNP完全ではない. 釈迦に説法終わり.

付記: PageRankを求める問題がPに入るかどうか.

適当な推移確率行列Aが与えられたとする. まずは, 愚直に固有値を求める.

• 特性多項式を作る→上三角化して対角成分を掛けるだけ. 上三角化は, Pに入る.
  • 推移確率行列に適当な整数を掛けて, 各要素を整数にしておく.
    • 列ベクトルを全部見て, 分母の最小公倍数を掛ける. この最小公倍数は精々2^{O(n)}なので大丈夫.
  • 上三角化の際に多項式の演算が入ってくるが, 次数は高々nで抑えられる.
• Z上の1変数多項式の因数分解は多項式時間で出来る. (C上でも大丈夫だった筈)

ということなので, 最大固有値を求める問題はPに入る.
で, 最大固有値λを求めたので, あとはそれを使って(A-λI)x=0を解いてやる. これももちろんPに入る.
結局, PageRankを求める問題はPに入る.

ページランクは二乗に比例だからNP完全じゃないよ。
Posted by 鈴木健 at 2006年12月17日 13:05

コメント欄で既に指摘されていた(;´Д｀)