# Are there any FNP-complete problems with a unique solution?

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$$.

• Specifically let's talk about the FNP version of the problem. Are there any FNP-complete problems where there is at most 1 y such that P(x, y)? Nov 16 '21 at 17:19
• Edited the question to reflect this. Nov 16 '21 at 17:22
• The UP complexity class seems related. Nov 16 '21 at 17:48

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.

• I'm asking if there is any such NP-complete problem with a unique solution, not about a specific NP complete problem. Nov 16 '21 at 17:20
• Or more specifically, FNP-complete problem. Nov 16 '21 at 17:20
• Oh, we are picky. Just assume the answer wasn’t meant for you, but for everyone else having the same question. Nov 16 '21 at 17:25

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 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 and $$x^2 \equiv a\mod b$$?

Is both FNP-complete and has a unique solution.

• Interesting. Has the paper been peer-reviewed and published somewhere? The same author also claims to have proved that $P \neq NP$... Nov 17 '21 at 22:41
• He also claims to have proven P = NP. I'm going to dismiss him as crank, although the proof for UP = NP seems reasonable, but I'll have to check through it more carefully. Nov 18 '21 at 4:10