3
$\begingroup$

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:

Computation tree example slide of P vs. NP

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?

$\endgroup$
  • 5
    $\begingroup$ No, non-determinism is not parallelism. Some explain it that way, but (imho) this intuition is flawed in bad ways. $\endgroup$ – Raphael Oct 16 '16 at 18:54
  • 1
    $\begingroup$ @Raphael I can't help thinking that comment would be a lot more enlightening if you spent a sentence or two summarizing why parallelism is a bad intuition. $\endgroup$ – Daniel Wagner Oct 17 '16 at 13:18
  • 1
    $\begingroup$ @DanielWagner I agree. If I had the time, I'd have written an answer. My answer here does not add a lot, either. Let's just say that students exposed to the "parallelism intuition" are likely to misconstrue non-determinism as an algorithmic as opposed to a descriptive concept; they will use deterministic intuition on non-determinism. That's just my experience. Also, you can model parallelism explicitly and the result looks nothing like non-determinism for obvious reasons. $\endgroup$ – Raphael Oct 17 '16 at 19:59
3
$\begingroup$

Your description of NP is still missing the accept criterion. For example you might decide to accept the input exactly in case all computation paths accept. This would give you the class coNP instead of NP. Or you might decide to accept the input exactly in case half of the computation paths accept. But for NP, the accept criterion is that there exists at least one computation path which accepts. Other than that, your parallelism model of NP is perfectly fine. And yes, the deterministic machine can simulate the computation of the non-deterministic machine in $O(2^n)$ time!

$\endgroup$
  • $\begingroup$ I suppose it's probably $O(|Σ|^n)$ rather than $O(2^n)$. $\endgroup$ – Daniel Wagner Oct 16 '16 at 21:41
  • $\begingroup$ "Other than that, your parallelism model of NP is perfectly fine. " -- I disagree. In a deterministic parallel world, every computation would check all the nodes (unless it recognizes success early and terminates) while no single non-deterministic computation does check more than one branch. Also, cost measures would be very different. $\endgroup$ – Raphael Oct 17 '16 at 20:01
  • 1
    $\begingroup$ @Raphael If you look at the image Nondeterministic Running Time in the question, then that part with the cost measures is already addressed. The real shortcoming of this answer is highlighted by "Edit: If we make the addition that one of the paths are guaranteed to accept, then is the machine now equivalent to NP?" This answer failed to make the distinction between a machine model and a problem class sufficiently clear. After reading his other questions, I decided to answer no further question from him, and wait until he learned it by himself. $\endgroup$ – Thomas Klimpel Oct 17 '16 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.