Isn’t it proof enough? Using the Sudoku example: there are certainly different levels of difficulties, depending on how many numbers are set in the beginning and other parameters. Checking if the solved answer is correct, is always the same “difficulty” - thus there is no correlation between the difficulty of the puzzle at the beginning and checking the Correctness. Some people might not be able to solve it, but they certainly can check if the solution is right
Too soon!