クラスNPの新しい特徴づけ - 確率的検査可能証明と近似問題 -

もっとも代表的な計算機のクラスである NP 問題に対して、最近、まったく新しい特徴づけが与えられ話題になっている。この理論について解説するとともに、近似問題への応用を述べる。

すみません、それです！http://ci.nii.ac.jp/naid/110002762960　もっと新しい解説論文があるかもしれません。 RT: @metaphusika 太田さん岡本さんを検索してみましたが論文「クラス NP の新しい特徴づけ」(1994)のことでしょうか？

1 @ronbuntter