In the last post,we saw a lower bound for bit probing (specifically, extracting the lower-most bit of a number) in the PRAM-without-bitops model. Now clearly this can be computed efficiently in P, so why isn't this enough of a proof for the separation of the two classes ?
The answer is subtle. In a PRAM model, excluding bit operations is a nontrivial restriction, because, as we saw, there's no parallel-efficient way of extracting bits from a word without bit operations. However, in P, this is not true. In time linear in the bitlength, we can extract every single bit, and then carry on. Thus, P-with-no-bitops is as powerful as P itself !
Mulmuley argues that the "correct" notion of excluding bit operations in P is that of an algorithm that might run in time that depends on the bit length, but without bitops, in the way that algorithms like the ellipsoid method work. But an easier approach is to exclude algorithms whose run time depends on the bit length, yielding the class of strongly polynomial algorithms. Note that this class (which he calls SP) still contains the P-complete problems max-flow and min-cost flow.
Once we do that, extracting bits is no longer an "easy" operation in SP. The "input size" is 1, and so any bit-extracting algorithm is only permitted a constant number of steps when extracting a bit. Therefore, the apparent separation doesn't really hold.
Formally, what is proved in this paper is that SP strictly contains C (the class of PRAM-without-bitops algorithms), via the separation result for max flow.
I'm afraid I don't follow.
ReplyDeleteEven if Mulmuley is proving the stronger result SP \neq PRAM-without-bitops, don't we still trivially(?) conclude from your last post that P \neq PRAM-witout-bitops?
I think the argument is something like this.
ReplyDeleteIf we weaken a class C enough, we can show that P \neq C. The point is that since we want to separate sequential from parallel, we want a "strong enough" parallel class and a "weak enough" sequential class.
Since max flow is P-complete (i.e it's strong in P), and in SP (i.e in the "weaker class"), it justifies consider SP as the correct sequential analog for PRAM-without-bitops. As he argues, P-without-bitops is meaningless as it stands.
Bottomline: using the bit extraction lower bound to say that we're done is sort of "cheating by playing games with bits". Using SP truly puts the sequential/parallel gap to the test.