What you want for asymmetric cryptography is "always hard to solve, easy to verify". Only a very small number of problems are believed to fall in this category, including factoring and discrete logarithm.

It's far more common to have problems that are "sometimes easy to solve, sometimes hard to solve, easy to verify". That describes this problem as well as most NP-hard problems that with good heuristic solutions. The problem is those "sometimes easy to solve" cases break your cryptography!