patternMinor
NP with a parallelism model?
Viewed 0 times
withparallelismmodel
Problem
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,
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,
Solution
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!
Context
StackExchange Computer Science Q#64679, answer score: 4
Revisions (0)
No revisions yet.