How much complexity difference can there be between finding a solution to a Sudoku puzzle and PROVING that the solution is the unique solution?
Yato and Seta show that for every constant $m$, given $m$ solutions to a Sudoku puzzle, it is NP-complete to determine whether there is another solution. They show that the same property is satisfied by other puzzles as well.