Saturday, July 6, 2013

Formal and Vernier Turing machine NP ( complexity ) Hypothesis -

Verifier-based definition
In order to explain the verifier-based definition of NP, let us consider the subset sum problem: Assume that we are given some integers, such as {−7, −3, −2, 5, 8}, and we wish to know whether some of these integers sum up to zero. In this example, the answer is "yes", since the subset of integers {−3, −2, 5} corresponds to the sum (−3) + (−2) + 5 = 0. The task of deciding whether such a subset with sum zero exists is called the subset sum problem.

take the sum of the absolute value negative numbers and compare the difference with the sum of the positive numbers


If: X = + ; Then : Assign X to set (+)
If: X = - ; Then : Assign Y to set (-)


sum of | set(-vars)|  = or =/= to sum of set(+vars)
or; (sum of set(+)) - (sum  of | set (-) |) = X Does X =  0 Y/N
-Lionel Reemus Wrongsbury
    "Luscious Lucious Seamus Reemus"
-- I do the typewriter aspect, thanks computer chaps

    •    For all x and y, the machine M runs in time p(|x|) on input (x,y)


Set Y;X;L Max to 1, Min to 0
Y=1
|
|
|
|
_______________X=1
\
 \
  \
   \
    \
     \
       L=1
P=Time ………………………………….
In instance of X, Log P Time, correlate

    •    For all x in L, there exists a string y of length q(|x|) such that M(x,y) = 1

If x in L ,  calc (x, (  (|q|  x = y) )
    •    For all x not in L and all strings y of length q(|x|), M(x,y) = 0


take the sum of the absolute value negative numbers and compare the difference with the sum of the positive numbers
sum of | set(-vars)|  = or =/= to sum of set(+vars)
or; (sum of set(+)) - (sum  of | set (-) |) = X Does X =  0 Y/N
If x = 1 then y = (+q) if x = 0 then y = ( -q )

For large numbers greater than 1 or 0 perhaps use a percentile scale to gradate the numbers.?

No comments:

Post a Comment