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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.