2004-08-12 どうでも良いこと NP-hard(なんちゃら-hard)の意味を初めて知った。 NPに属するどの問題よりも計算量が多い問題(NPに属するとは限らない) ということだったのか。 用語自体はちょこちょこ見かけたのだが、使ってた教科書に 載ってなかったから分からないままだった。 ということはNP-completeはNP-hardかつNPの元であるような問題か。 うーむ。