On NP-Completeness for Linear Machines

AbstractWe consider linear and scalar versions of the Blum–Shub–Smale model of computation over the reals. The permitted computing operations of linear machines are addition and multiplication by constants. The scalar machines can only multiply by constants. The size of an input is its dimension, and the cost of any instruction is one. For each of these structures we consider DNP and NP, the corresponding complexity classes with respect to digital nondeterminism and standard real nondeterminism, respectively. We give DNP- and NP-complete problems for linear and real scalar machines. On the other hand, we show that the NP-class restricted to scalar machines over the integers with equality-tests does not own a complete problem