0
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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)? $\endgroup$ Nov 16, 2021 at 17:19
  • $\begingroup$ Edited the question to reflect this. $\endgroup$ Nov 16, 2021 at 17:22
  • 1
    $\begingroup$ The UP complexity class seems related. $\endgroup$
    – Steven
    Nov 16, 2021 at 17:48
1
$\begingroup$

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.

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

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.

$\endgroup$
2
  • $\begingroup$ Interesting. Has the paper been peer-reviewed and published somewhere? The same author also claims to have proved that $P \neq NP$... $\endgroup$
    – Steven
    Nov 17, 2021 at 22:41
  • $\begingroup$ 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. $\endgroup$ Nov 18, 2021 at 4:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.