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?
3
-
5$\begingroup$ 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. $\endgroup$– Emil JeřábekDec 7, 2022 at 17:11
-
2$\begingroup$ 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. $\endgroup$– Dan DoelDec 7, 2022 at 18:06
-
$\begingroup$ en.wikipedia.org/wiki/… $\endgroup$– D.W.Dec 7, 2022 at 18:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.)
