A Shift-free Characterization of NP within Interval-valued Computing
What is it about?
Interval-valued computing is a relatively new computing paradigm that uses finite union of intervals of the unit interval [0,1) as data. This a deterministic, straight-line paradigm which is also massively parallel, since logical operations (e.g., negation, disjunction and conjunction) are executed in one step for each position of [0,1). In fact, these operations are the complement, the union and the intersection of interval-values. We start the computation with the interval-value [0,1/2). Then we use the product operator, which is a kind of zooming of the interval value (e.g., to compress it). The product is used only in the initial phase of the computation. Then only the logical operations are used. We show in the paper that all problems in NP can be decided by polynomial size of computation in this paradigm in the described way.
Why is it important?
New computing paradigms give new ideas to solve computationally hard problems (at least in theory). Classical complexity classes, like NP, play essential role in computer science. By establishing connections between these fields, one may have a better understanding of classically difficult and complex problems, and also gets more information about the classical and the new computing paradigm.