If you can solve something easily, then you can also verify its solutions easily.

It is a typo. It should say "but potentially extremely difficult for computers to solve."