今月の日経サイエンスに”量子コンピュータも苦手な問題”という特集がある。既存のコンピュータでもクラス P の問題は効率良く（多項式時間で）解くことができる。多項式時間でというところが曲者で O(n^100) でも n の多項式なので効率が良いという話になる…