Suggest edit — Non-Deterministic Computation

Title

Name

Note

---
title: "Non-Deterministic Computation"
type: concept
related: [Non Polynomial Time, Non Deterministic Turing Machines, Np Complete, P Vs Np]
source: https://www.jemoka.com/posts/kbhnon_deterministic_computation/
confidence: high
status: active
---

&hellip;building blocks of Non-deterministic Turing Machine. Two transition functions:
\begin{equation} \delta_{0}, \delta_{1} : Q \times \Gamma^{k} \to Q \times \Gamma^{k-1} \times \qty {L, R, S}^{k} \end{equation}
At every point, apply both of these separate functions/branch on both. Some sequences lead to \(q_{\text{accept}}\), and some others lead to \(q_{\text{reject}}\).
We accept IFF exists any path accepts =&gt; we reject IFF all path rejects.
why NP is awesome &ldquo;what a ridiculous model of computation!&rdquo;
Yes, so that&rsquo;s why P vs. NP is so frustrating as a problem; if NP is indeed ridiculous, should be able prove P != NP verifier formulation of NP NP captures many, many important problems: SAT, Hamiltonian path problem, clique problem, etc. etc. the notion of NP-Completess: &ldquo;if any of these problems in \(P\), then all of everything in \(NP\) are in \(P\)&rdquo;