The problem of estimating algorithmic complexity comes to mind. Easy to verify, hard to improve.