Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?

Question

This relates to an answer for this question.

The opinion said that:

Personally, I don’t see much value in coding interviews. The problems I’ve seen asked as coding questions have been (for the most part):

asked by a person who has one specific solution in mind and is unable to recognise an alternative answer or even a better answer (Note: I actually faced this one time - the clown kept telling me I was wrong. For a metaphor of this, see 1 below);

Imagine a coding question to solve traveling salesman in non-polynomial time (a stupid question because it’s not realistic but I’m going for a metaphor here). Imagine, instead, you solved a different NP-complete problem in non-polynomial time and the interviewer wouldn’t accept that solving any one NP-complete problem in non-polynomial time solves them all. If the interviewer lacks the ability to grasp a great answer, then the candidate offering the great answer is filtered out.

I've read in Geeksforgeeks that:

The interesting part is, if any one of the NP complete problems can be solved in polynomial time, then all of them can be solved.

From what I understand, the interviewer gave a TSP problem, to be solved in brute-force approach. The interviewee solved a different problem of the same NP-completeness level in non-polynomial time (maybe using brute-force approach) too. And, literally what I quote from the Geeksforgeeks above.

My questions:

• Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?
• Are the solutions (in non-polynomial time) for NP-complete problems universal (one solution can be used for all)?
• Why would the interviewee solve another problem instead of the given problem? Or am I misunderstanding something? Is it to show that the approach is universal?

Thank you in advance for your insights.

Answer 1

If you solve a Problem that is NP-complete the solution to this problem can not be applied instantly to any other Problem that is NP-complete. However, the problem that you solved might be used to find a solution for other problems in NP.

For example:

• If you can solve the TSP Problem your an adaption of your solution could also solve the problem of finding a hamiltonian circle in a graph
• If you can solve the hamiltonian circle problem an adaption of your solution could also solve the long path problem
• ...

So your solution can not be directly used to solve other problems. But if you found a solution for a problem that is NP-complete this implies that there are solutions in P for every problem that was believed to be NP-complete. This is because NP-completeness is defined as follows:

A problem P is NP-complete if it is NP-hard and the problem lies in NP

Beeing NP-hard means that every other problem P' that is NP-complete can be reduced to the problem P (meaning exactly that if you could find a solution for P you could also find oune for P')

The answer to your second question is simply "No".

The only reason for a cancidate to solve another problem that is NP-complete is that he could not find a solution for the given problem but for the other problem. And in addition he knows how to modify the problem he is abel to solve in such a way that he finds a solution for the given problem.