0
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ Are you familiar with the definitions of NP, NP-complete, and the like? If not, I would recommend reviewing our reference question. $\endgroup$ Sep 21, 2020 at 13:24
  • $\begingroup$ Thank you, Prof. Yuval. Will go through your recommendation, and edit the question or reply back here if necessary. $\endgroup$
    – kate
    Sep 21, 2020 at 14:49

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ So it means, a solution of a problem A, if cannot be used directly to solve another problem B, chances are the solution can be used with some modification. Thank you for your easy-to-understand insight and important clarification. $\endgroup$
    – kate
    Sep 23, 2020 at 5:03

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.