The complexity of algorithms that find unique solution for an NP-complete problem (the input is guaranteed to have a unique solution) seems to shed light on the hardness character of different NP search problems. Two well known examples are the unique k-SAT search problem and solving Sudoku puzzle. As far as I know, the best algorithms for both are still exponential. I am interested in large gaps (if any exists) between the complexity of search algorithms for different NP-complete problems.
What complexity class does represent such search problems? Is there a survey paper of algorithms for such search problems?
This is motivated by two posts, NP-Complete problems that admit an efficient algorithm under the promise of a unique solution, and Examples where the uniqueness of the solution makes it easier to find.
