The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+4 votes

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

- $3$SAT can be solved in polynomial time.
- Halting problem can be solved in polynomial time.
- Factoring can be solved in polynomial time.
- Graph isomorphism can be solved in polynomial time.
- Travelling salesman problem can be solved in polynomial time.

+8 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 t**o 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.**

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.4k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 819
- Others 1.1k
- Admissions 244
- Exam Queries 419
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,156 questions

36,980 answers

92,146 comments

34,822 users