GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
146 views

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

  1. 3SAT 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.

 

asked in Algorithms by Veteran (38.7k points)  
recategorized by | 146 views
i guess halting problem is NPH problem so it will be not implied.
more precisely halting problem is outside NP and also undecidable.
Yes, it is proved that no one can ever solve Halting Problem.

Option B is correct.

1 Answer

+7 votes
Best answer

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.

answered by Veteran (13.1k points)  
selected by

Related questions



Top Users Sep 2017
  1. Habibkhan

    6362 Points

  2. Warrior

    2234 Points

  3. Arjun

    2212 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1552 Points

  10. rishu_darkshadow

    1512 Points


25,991 questions
33,561 answers
79,414 comments
31,029 users