That's true of every np-complete (or similar class) problem: it's easy to verify that a solution work, but hard to find it in the space of possible solutions.

Reportedly, quantum computers can help us with some problems of that kind.