# Why if non determinism adds no power at all to DFAs or to Turing machines, why is it that most people beleieve P != NP [closed]

During Theory of Computation or Automata Theory or the equivalent class at my University, I was shown that non deterministic and deterministic automata can solve the exact same set of problems, then why is the set of problems P not the same as NP or at least assumed by most people not to be true? Since we have a construction to go from NFA to a DFA and we know that non determinism does notmake turing machines any more powerful, why do we not have such a thing from NP to P?

• It’s not true (or at least not clear, unless you believe P = NP) that nondeterminism does not make Turing machines more powerful. Deterministic Turing machines accept the same languages as nondeterministic Turing machines, yes, but using exponentially longer time. Dec 7, 2022 at 17:11
• Note that a similar thing is true of finite automata. NFAs and DFAs accept the same languages. But, the minimal DFA to accept a language may require exponentially more states than are required for an NFA to accept the same language. So the finite automaton case actually leads toward P≠NP. Dec 7, 2022 at 18:06
• en.wikipedia.org/wiki/…
– D.W.
Dec 7, 2022 at 18:15

The equivalence you're talking about is a very coarse one. The DTM $$A$$ corresponding to an NTM $$B$$ in the obvious way will accept the same language as $$B$$, but it will do so vastly more slowly. Since the P vs. NP question is all about runtime ("D-machines in polytime vs. N-machines in polytime," not "D-machines vs. N-machines"), this isn't something we can ignore!
Now you might hope that nonetheless there is a way to get from this construction - or at least, the result this construction gives us - to a proof that $$\mathsf{P}=\mathsf{NP}$$. However, in a precise sense this can't happen: we can find an oracle $$X$$ such that $$\mathsf{P}^X\not=\mathsf{NP}^X$$, but deterministic machines with $$X$$ as an oracle and nondeterministic machines with $$X$$ as an oracle still have the same overall computational possibilities (I hesitate to say "power" here), and for exactly the same reason.
(The existence of such an $$X$$ is one half of the Baker-Gill-Solovay theorem; the other half says that there is a $$Y$$ such that $$\mathsf{P}^Y=\mathsf{NP}^Y$$.)