今回扱う定理について 今回示す問題は、固有値にまつわる有名な定理であり、 Min-Max Theorem と呼ばれている。 Min-Max Theorem: 定理の紹介 はレイリー商と呼ばれている。 証明に入る前にレイリー商の性質について述べる。レイリー商は、引数が 行列 の固…

はじめに 大学で学んだ多項式時間還元について、日本語記事でわかりやすいものが見つからなかったため、ここに記す。数ヶ月後におそらく試験で出題されるので、その試験対策としても。 blog 末尾でも述べるつもりであるが、Garey と Johnson による黒い本 Co…