edited by
1,661 views
4 votes
4 votes

Which of the following is not implied by $P=NP$?

  1. $3$SAT can be solved in polynomial time.
  2. Halting problem can be solved in polynomial time.
  3. Factoring can be solved in polynomial time.
  4. Graph isomorphism can be solved in polynomial time.
  5. Travelling salesman problem can be solved in polynomial time.
edited by

1 Answer

Best answer
11 votes
11 votes

I believe Umang is right, option B is the correct answer.


Intractability : We are looking for EFFICIENT algorithms.

Intractable Problems are problems that are decidable, although the algorithm to decide that problem might be efficient (P) or inefficient (NP), but at least an algorithm exists to solve these problems.

Here we talk about efficient vs inefficient computations.

Thus the language of problems in P and NP classes is the language of Decidable Problems i.e. Recursive Language.


Undecidability: We are looking for algorithms.

Undecidable Problems are problems for which there is no algorithm to solve these problems.

Here we talk about what can or can not be computed.

The language of Undecidable Problems are "Recursively Enumerable but not recursive languages" & "Not Recursively Enumerable Languages".


Clearly we can talk about the intractability of any problem if we know at least one algorithm to solve the problem, if there is no algorithm to solve a problem how can we talk about efficiency?


Halting Problem is undecidable.

I guess, all other problems mentioned here are decidable.

I don't know the most efficient algorithms to solve these problems but at least I can say that Brute force approach will work on all the other options except the Halting Problem.


What P = NP implies?

"Any problem that is solved by a non deterministic Turing machine in polynomial time also be solved by some deterministic Turing machine in polynomial time, even if the degree of the polynomial is higher."

and

There is neither a Non Deterministic Turing Machine nor Deterministic Turing Machine that can solve the Halting Problem.


So any inference about P & NP is not going to affect the solvability of Halting Problem, since it is undecidable.

Answer:

Related questions

15 votes
15 votes
2 answers
3