Thursday, June 27, 2013

Uniquely solvable puzzles

We know that most "interesting" one-player games (or puzzles) are NP-hard. Read as:
given a puzzle, it's hard to decide whether it has a solution or not.

This question (seemingly) has little to do with the following one:
given a puzzle which is guaranteed to have exactly one solution, compute the solution.

Note that the standard reduction techniques do not preserve the number of solutions (e.g. no UP-complete problem is known as of today). I know that if we drop "exactly" (and write "at least" instead), then we get the class TFNP. But I do not know how this class of "uniqely solvable" problems is called and I'm interested in the current state of the art in this topic :-)

I could use someone to collect and read the literature for me ;-)

No comments:

Post a Comment