I was reading up on something called the PRAM model without bit operations. What exactly does it mean that this PRAM model cannot do bit operations? I can't find a straightforward definition anywhere.
Surely the different processors will still be able to do all sorts of stuff with bits. The reason why I am asking is that the max-flow problem (which is in P cannot be solved in this model using a polynomial number of processors. So in fact it is a non-trivial implication of the conjecture that $P \neq NC$. So it is further "evidence" of the $P \neq NC$ conjecture.

  • $\begingroup$ "which is in P cannot be solved in this model using a polynomial number of processors" -- that's conjecture, as you state in the next sentence. $\endgroup$ – Raphael Apr 15 '16 at 13:13
  • 1
    $\begingroup$ Hopefully your source has some citations. There are many variants of the RAM model (also called the pointer machine model). Perhaps the model that was meant is the real RAM model, in which access to numbers is limited to arithmetic operations and comparisons. $\endgroup$ – Yuval Filmus Apr 15 '16 at 13:41
  • $\begingroup$ Can you please tell us what you were reading that made you think that PRAM model cannot do bit operations (give us a full reference to the source, and a link if possible)? $\endgroup$ – D.W. Apr 15 '16 at 16:49
  • $\begingroup$ I was referring to some papers by Ketan Mulmuley. If you want a brief overview you can read his paper in which he outlines a research program called geometric complexity theory. It is called "The GCT program towards the P vs. NP problem" and can be found on his homepage. There you can also find a paper in which he proves this special case of $P \neq NC$. $\endgroup$ – Leo Apr 16 '16 at 8:45

Without further information, it's hard to tell exactly. However, to the best of my knowledge, bit operations may be intended as follows. Consider the problem of finding the maximum element in an array of $n$ real numbers. This problem can be solved by an EREW algorithm in $\Omega(\lg n)$; moreover, no CREW algorithm can do any better.

However, this problem can be solved in $O(1)$ time with $n^2$ processors using a common-CRCW algorithm (in this model, when several processors write to the same location, they all write the same value). The key point here is that a CRCW PRAM is capable of performing a boolean AND of $n$ variables in $O(1)$ time with $n$ processors (which allows overcoming the $\Omega(\lg n)$ lower bound). I think that bit operations may refer to this powerful AND capability of a common-CRCW.

Additional information regarding the FAST-MAX algorithm can be found in the first edition of CLRS Introduction to Algorithms, chapter 30 (ALGORITHMS FOR PARALLEL COMPUTERS).

  • $\begingroup$ The fact that the OP mentions maximum flow leads me to conjecture that by bit operations, they meant bit operations. In the context of maximum flow you can consider algorithms running on the real RAM, in which you are not allowed to peek at individual bits. $\endgroup$ – Yuval Filmus Apr 15 '16 at 22:35

On page 1461 of "Lower Bounds in a Parallel Model without Bit Operations," Mulmuley says:

It is like the usual PRAM model, the main difference being that it does not provide instructions for any bit operations such as $\land$,$\lor$,or extract-bit.

The model is explicitly specified in section 2.1.

The reason I think this result ($\textsf{P}\neq\textsf{NC}$) in this model is interesting is---although this model does not allow bit-operations---it still allows the time to depend on bitlengths. Also, this model is powerful enough to compute the determinant (see paragraph "Arithmetic PRAM model." on page 1469)!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.