1
$\begingroup$

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.

$\endgroup$
1

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.