Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Are there any FNP-complete problems where there's only one possible solution?
For example, the travelling salesman problem can have multiple routes all shorter than $X$. There's only one shortest route, but it can't be validated that a given route is the shortest route in polynomial time.
I'm interested in either such an FNP-complete problem, or a proof this is impossible.
Are we talking about solutions or certificates? Since NP-complete problems are decision problems, a solution (to each instance) is always either "yes" or "no" and hence it's unique.
If we are talking about certificates, then no. Each yes-instance of a NP-complete problem admits infinitely many polynomial-length certificates. Indeed if $c$ is a yes-certificate and $T$ is a verifier, then you can always consider the certificate obtained by prepending, e.g., any number $k$ of zeros to $c$. The corresponding verifier is obtained from $T$ by first dropping the leading $k$ zeroes and then simulating $T$.
Travelling salesman problem: Given a number of locations and distances, we can ask: 1. Is there a tour of length <= L? 2. Is L the length of the shortest tour? 3. Which is a shortest tour?
The first is obviously in NP. The second is obviously in co-NP. The third is not a decision problem. So there is no certificate for “is R the shortest route” unless NP = co-NP.
But take “Hamiltonian path”: Given n locations which are all connected or not connected, is there a path connecting them all?
Apart from the fact that there are 2n essentially equal paths, it seems quite possible that some instances will have exactly one connecting path and therefore a unique certificate based on the path.
This question is knows as UP versus NP
EDIT: turns out the author of this paper is a crank, so you can ignore the rest of this answer.
Surprisingly enough it's been proved that UP=NP!
The Quadratic Congruences problem asks if, for constants $a$, $b$, and $c$, there exists $x$ such that $x<c$ and $x^2 \equiv a\mod b$. It is known to be NP-complete even if we know the prime factorization of $b$.
The paper shows that given any solution to this problem we can find the smallest positive solution in polynomial time if we have the prime factorization of $b$. This means that the question:
For constants $a$, $b$, and $c$, what is the smallest positive $x$ such that $x<c$ and $x^2 \equiv a\mod b$?
Is both FNP-complete and has a unique solution.
