С некоторым удивлением узнал, что японские кроссворды (нонограммы) -- NP-полная задача (японские учоные доказали!). Однако есть мощные эвристики, часто ускоряющие процесс до P.
(так-то я всегда был убеждён, что NP = P, а скоро и вся мировая криптография прочувствует :)