<p>The equivalence you're talking about is a very coarse one. The DTM <span class="math-container">$A$</span> corresponding to an NTM <span class="math-container">$B$</span> in the obvious way will accept the same language as <span class="math-container">$B$</span>, but it will do so <strong>vastly</strong> more slowly. Since the P vs. NP question is all about <em>runtime</em> (&quot;D-machines in polytime vs. N-machines in polytime,&quot; not &quot;D-machines vs. N-machines&quot;), this isn't something we can ignore!</p>
<p>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 <span class="math-container">$\mathsf{P}=\mathsf{NP}$</span>. However, in a precise sense this can't happen: we can find an oracle <span class="math-container">$X$</span> such that <span class="math-container">$\mathsf{P}^X\not=\mathsf{NP}^X$</span>, but deterministic machines with <span class="math-container">$X$</span> as an oracle and nondeterministic machines with <span class="math-container">$X$</span> as an oracle still have the same overall computational possibilities (I hesitate to say &quot;power&quot; here), and for exactly the same reason.</p>
<p>(The existence of such an <span class="math-container">$X$</span> is one half of the <strong>Baker-Gill-Solovay theorem</strong>; the other half says that there is a <span class="math-container">$Y$</span> such that <span class="math-container">$\mathsf{P}^Y=\mathsf{NP}^Y$</span>.)</p>

CC BY-SA 4.0
2022-12-07T21:45:01.637Z
2022-12-07T21:45:01.637Z
Noah Schweber
<p>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?</p>

CC BY-SA 4.0
2022-12-07T17:11:11.653Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-12-07T18:06:08.827Z
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.
Dan Doel
CC BY-SA 4.0
2022-12-07T18:15:56.693Z
https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_%E2%89%A0_NP_or_P_=_NP
D.W.
<time-complexity><np><p-vs-np>
Why if non determinism adds no power at all to DFAs or to Turing machines, why is it that most people beleieve P != NP
user68029
# Why if non determinism adds no power at all to DFAs or to Turing machines, why is it that most people beleieve P != NP

(Asked by: username_0 on 2022-12-07)

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?

**Tags:** time-complexity, np, p-vs-np

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_%E2%89%A0_NP_or_P_=_NP  

---

## 1 answers

### Answer by username_4 on 2022-12-07. Score: 2

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$.)


---

