こないだの話もあって、なんとなくその辺にあった『組合せ最適化 第2版 (理論とアルゴリズム)』 http://www.amazon.co.jp/dp/4621062026 という本のNP-困難性のあたりを眺めていたら、「決定問題は，その補問題がNP-困難であるとき，そしてそのときのみ，NP-困難である，ことに注意されたい」(p.439)と書いてあり、またのけ反りそうになった。周囲の人と話して、片方のNP-困難がcoNP-困難の誤植だろうということに落ち着いたけれど。

この間の話: 
https://plus.google.com/100215187201873478127/posts/HexRuzYrbui