Analysis Of Pram Instruction Sets From A Log Cost Perspective

The log cost measure has been viewed as a more reasonable method of measuring the time complexity of an algorithm than the unit cost measure. The more widely used unit cost measure becomes unrealistic if the algorithm handles extremely large integers. Parallel machines have not been examined under the log cost measure. In this paper, we investigate the Parallel Random Access Machine under the log cost measure. Let the instruction set of a basic PRAM include addition, subtraction, and Boolean operations. We relate resource-bounded complexity classes of log cost PRAMs to complexity classes of Turing machines and circuits. We also relate log cost PRAMs with different instruction sets by simulations that are much more efficient than possible in the unit cost case. Let LCRCW k (CRCW k ) denote the class of languages accepted by a log cost (unit cost) basic CRCW PRAM in O(log k n) time with polynomial in n number of processors. We position the log cost PRAM in the hierarchy of paralle..