The RS-vector machine is a vector machine based on the vector operations called repeat and stretch. It is known that they generally speed up, according to a single parameter called the expansion factor, several sequential complexity classes over polynomial space to polynomial time. In this paper, the authors investigate the computational power of the model for more concrete problems. RS-vector algorithms are given which can solve typical NP complete problems, i.e., satisfiability, knapsack, partition, vertex cover, clique and exact cover problems in O(n) time, k-colorable problem in O(nlogk) time, and Hamilton circuit and traveling salesman problems in O(nlog2n) time. It should be emphasized that vector machines are, as compared with other models like PRAMs, completely of SIMD-type and their communication facilities are no more than those represented by repeat and stretch. The present results show that such a restricted model can solve a wide range of NP problems in almost linear time. [In Japanese.]
