Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Visit Stack Exchange
Stack Internal
Knowledge at work
Bring the best of human thought and AI automation together at your work.
Explore Stack InternalAre there any NPFNP-complete problems where there's only one possible certificatesolution?
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 NPFNP-complete problem, or a proof this is impossible.
Are there any NP-complete problems where there's only one possible certificate?
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 NP-complete problem, or a proof this is impossible.
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 there any NP complete-complete problems where there's only one possible certificate?
For example, the travelling salesman problem can have multiple routes all shorter than X$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 NP complete-complete problem, or a proof this is impossible.
Are there any NP complete problems where there's only one possible certificate?
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 NP complete problem, or a proof this is impossible.
Are there any NP-complete problems where there's only one possible certificate?
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 NP-complete problem, or a proof this is impossible.
Are there any NP complete problems where there's only one possible certificate?
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 NP complete problem, or a proof this is impossible.
