ON THE POWER OF SOME PRAM MODELS

Abstract

The focus here is the power of some underexplored CRCW PRAMs, which are strictly more powerful than exclusive write PRAM but strictly less powerful than BSR. We show that some problems can be solved more efficiently in time and/or processor bounds on these models. For example, we show that n linearly-ranged integers can be sorted in O(logn/loglogn) time with optimal linear work on Sum CRCW PRAM. We also show that the maximum gap problem can be solved within the same resource bounds on Maximum CRCW PRAM. Though some models can be shown to be more powerful than others, some of them appear to have incomparable powers.

Keywords:

• PRAM; BSR
• Time and processor bounds
• Simulation
• Sorting @Classification Categories: F.l.l
• F.1.2
• F.2.2

Additional information

Notes on contributors

LIN CHEN

Corresponding author.