Can we think of NP using a parallelism model instead of using a "checking relation" without loss of generality?
From what I understand from the problem statement given by Stephen Cook,
The notation NP stands for “nondeterministic polynomial time”, since originally NP was defined in terms of nondeterministic machines (that is, machines that have more than one possible move from a given configuration). However, now it is customary to give an equivalent definition using the notion of a checking relation, which is simply a binary relation R ⊆ Σ ∗ × Σ ∗ 1 for some finite alphabets Σ and Σ1. We associate with each such relation R a language LR over Σ ∪ Σ1 ∪ {#} defined by LR = {w#y | R(w, y)} where the symbol # is not in Σ. We say that R is polynomial-time iff LR ∈ P. Now we define the class NP of languages by the condition that a language L over Σ is in NP iff there is k ∈ N and a polynomial-time checking relation R such that for all w ∈ Σ ∗ ,w ∈ L ⇐⇒ ∃y(|y| ≤ |w| k and R(w, y)), where |w| and |y| denote the lengths of w and y, respectively.
it appears that the definition of NP given here can be derived from the definition of non-deterministic Turing machines. From this lecture document from the University of Illinois:
Formally, a nondeterministic Turing machine has all the components of a standard deterministic Turing machine—a finite tape alphabet Γ that contains the input alphabet Σ and a blank symbol ; a finite set Q of internal states with special start, accept, and reject states; and a transition function δ. However, the transition function now has the signature δ: Q × Γ → 2 Q×Γ×{−1,+1} . That is, for each state p and tape symbol a, the output δ(p, a) of the transition function is a set of triples of the form (q, b,∆) ∈ Q × Γ × {−1,+1}. Whenever the machine finds itself in state p reading symbol a, the machine chooses an arbitrary triple (q, b,∆) ∈ δ(p, a), and then changes its state to q, writes b to the tape, and moves the head by ∆. If the set δ(p, a) is empty, the machine moves to the reject state and halts. The set of all possible transition sequences of a nondeterministic Turing machine N on a given input string w define a rooted tree, called a computation tree. The initial configuration (start, w, 0) is the root of the computation tree, and the children of any configuration (q, x, i) are the configurations that can be reached from (q, x, i) in one transition. In particular, any configuration whose state is accept or reject is a leaf. For deterministic Turing machines, this computation tree is just a single path, since there is at most one valid transition from every configuration.
This mentions the notion of a computation tree:
Thus, suppose I were to have a machine that was able to compute all of the non-deterministic branches in parallel such that the bounded running time is $O(poly(n))$. Is this an equivalent of a Turing machine such that a language that is accepted by this machine is within $NP$?
In a sense, we can also see that if a deterministic machine were to choose the "right" branch by chance that it's somewhat equivalent to the notion of an oracle. This seems like it's similar to the "checking relation" in the sense that we need only compute one branch's result in order to determine acceptance of the answer or rejection. Is this intuition right?
And, in addition, can the deterministic machine can simulate the computation of the non-deterministic machine in $O(2^n)$ time?
Edit: If we make the addition that one of the paths are guaranteed to accept, then is the machine now equivalent to NP?
