2
$\begingroup$

My first question here, I think this will be an easy one.

As for definition:

NP: NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine. (wiki)

P: P Contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. (wiki)

(a) I thought, that you can convert every Non-deterministic Turing machine into a equivalent deterministic Turing machine ?

I am not sure about that I know it is possible with NFA's to DFA's.

But if (a) is true, wouldn't that mean that P=NP?

|cite|improve this question
$\endgroup$
1
$\begingroup$

Yes, a non-deterministic Turing machine can be converted into an equivalent deterministic Turing machine, but it is not known that if a polynomial time non-deterministic Turing machine can be converted into an equivalent polynomial time deterministic Turing machine.

Note "equivalent" only means they accept the same language, it does not mean they run in the same time.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ ahh ok, but if it were possible then it would mean that P=NP ? $\endgroup$ – simplesystems Jun 16 '18 at 9:29
  • $\begingroup$ @simplesystems Yes. $\endgroup$ – xskxzr Jun 16 '18 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.