They’re not crosswords. But they are logic puzzles. Regarding your skill cap comment, even children’s jigsaw puzzles that have 4 pieces are still considered puzzles lol.

Wikipedia says NP-complete under “Nonograms in computing”.

https://en.m.wikipedia.org/wiki/Nonogram