NP hard
and NP Complete Problem:
NP stands for Non-deterministic Polynomial time. This means
that the problem can be solved in Polynomial time using a Non-deterministic
Turing machine. Basically, a solution has to be testable in
polynomial time. If that's the case, and a known NP problem can be solved using
the given problem with modified then the problem is NP complete.
The NP-class problems are divided as NP Complete and NP Hard.
·
NP-hard: is a class of problems
that are, informally, "at least as hard as the hardest problems in
NP". A problem H is NP-hard if and only if there is an Np-Complete problem L that is polynomial time Turing-reducible to H.
·
NP-complete: is a class of decision problems A decision problem L is NP-complete if it is in the set of NP problems and also in the set of NP-hard problems,these problems cannot be solved in the polynomial
time.
Instance: A (multi)set V = {v1; v2; ………Vn} of positive integer
numbers, and
a positive integer number S.
If we allow to
nondeterministically choose among the rules which occur in the neurons, then
the extended SN P system depicted in Figure 1 solves any given instance of
Subset Sum in a constant number of steps. We emphasize the fact that such a
solution occurs in the semi-uniform setting, that is, for every instance of
Subset Sum we build an SN P system that specially solves that instance.
Let (V = fv1; v2; : : : ; vng; S) be the instance
of Subset Sum to be solved.
In the initial configuration of the system,
the leftmost neurons contain (from top to bottom) v1. v2 ……. Vn spikes,
respectively, whereas the rightmost neurons contain zero spikes each. In the ¯next
step of computation, in each of the leftmost neurons of the SN P system
depicted in Figure 1 it is nondeterministically chosen whether to include or
not the element vi in the (candidate) solution B µ V ; this is accomplished by
nondeterministically choosing among one rule that forgets vi spikes
(in such a case, vi 62 B) and one rule that
propagates vi spikes to the rightmost neurons. At the beginning of the second
step of computation a certain number N = |B| of spikes, that corresponds to the
sum of the vi which have been chosen, occurs in the rightmost neurons. We have
three possible cases:
- N < S: in this case neither the rule a^*/a^Sà a; 0 nor the rule a^*=a^S+1 --> a; 1
(which
occur in the neuron at the top and at the bottom of the second layer,
respectively) thus
no spike is emitted to the environment;
- N = S: only the rule a^*/a^sàa and 0 fires, and emits a single spike to the environment. No further spikes are emitted;
- N > S: both the rules a^*/a^sàa and a^*=a^S+1 à a; 1 fires. The first rule immediately sends one spike to the environment, whereas the second rule sends another spike at the next computation step (due to the delay associated with the rule).
Figure 1 is as follows:
In order to look for a subset B is subset of V such that sum of b
belongs to B b = S,
the algorithm uses an n * (S + 1) matrix M whose entries are from {0,1}. It fill the matrix by
rows,starting from the first row. Each row is ¯filled
from left to right. The entry M[i; j] is ¯filled with 1 if and only if there exists a
subset of {v1,v2,…vi} whose elements sum up to j. The given instance of Subset Sum is thus a positive
instance if and
only if M[n; S] = 1 at the end of the execution. Since each entry is considered exactly once to
determine its value, the time complexity of the algorithm is proportional to n(S+1) = average(nS). This means that
the difficulty of the problem depends on the value
of S, as well as on the
magnitude of the values in V . In fact, let K = max(v1,v2,v3…vn S). If K is polynomial bounded with respect to n, then the above
algorithm works in polynomial time.On the other hand, if K is exponential with
respect to n,
say K = 2^n , then the
above algorithm may work in exponential time and
space. This behavior is usually referred to in the literature by telling that Subset Sum is a pseudo-polynomial NP-complete problem.
Conclusion:
The fact that in
general the running time of the above algorithm is not poly-nominal can be
immediately understood by comparing its time complexity with the instance size.
The usual size for the instances of Subset Sum is avarage(n logK), sincen for conciseness every \reasonable"
encoding is assumed to represent each element of V (as well as S) using a string whose
length is O(logK). Here all logarithms
are taken with base 2. Stated differently the size of the instance is usually
considered to be the number of bits which must be used to
represent in binary S and all the integer numbers which occur in V . If we would represent
such numbers using the unary notation, then the size of the instance would be
average(nK). But in this case we could write a program which first converts the
instance in binary form and then uses the above algorithm to solve the problem
in polynomial time with respect to the new instance size. We can thus conclude
that the difficulty of a numerical NP-complete problem depends also on the measure of the
instance size we adopt.
The
problem we mentioned above about the SN P system depicted in Figure1 is that
the rules a^vi àlambda and a^viàa^vi ; 0
which occur in the leftmost neurons, as well as those that occur in the
rightmost neurons, check for the existence of a number of spikes which may be
exponential with respect to the usually agreed instance size of Subset
Sum.
Moreover, to initialize the system the user has to place a number of objects
which may also be exponential. This is not fair, because it means that the SN P
system that solves the NP{complete problem has in general an exponential size with
respect to the binary string which is used to describe it; an exponential
effort is thus needed to build and initialize the system, that easily solves
the problem by working in unary notation (hence in polynomial time with respect
to the size of the system, but not with respect to its description
size) concerning traditional P systems that solve NP{complete
problems.
No comments:
Post a Comment