P vs NC V: Linear PRAMS II

This is where we left off last time:

If a set of inputs parametrized by d parameters is accepted in the linear PRAM model with p processors in t time, then there is a way of partitioning using hyperplanes, so that each cell of the resulting arrangement can be labelled 0 or 1 so that an input z is accepted iff it lies in a cell labelled with a 1.

The above lemma describes the geometric structure induced by an efficient computation on a linear PRAM. Now, we'll see how a high parametric complexity problem breaks this structure.
We will do this by demonstrating that such a problem has too many accepting and non-accepting inputs close to each other to allow for such a cell labelling with these few hyperplanes.

1. Setup

We start with some parametrized problem (with parameter ) with cardinality n and bitsize . Remember that the bitsize refers to the maximum complexity of the coefficients of expressions involving . Let the parametric complexity of this problem (as we defined earlier) be . For technical reasons, we will require that the problem under consideration be homogeneous (scaling values by a constant multiplies OPT by the same value); this does not change anything, since this is true for problems like min-cost flow and max-flow.

Each numeric parameter in the input can be expressed as some , and without loss of generality we will assume that u and v are integers. We will actually need all parameters to be integral, so thinking of as the rational , we can rewrite all such parameters in the form , yielding a new instance with the same combinatorial structure (again, homogeneity makes things easy).

We now have a two parameter system that describes an input to the problem. A third parameter will describe the threshold for this (optimization) problem. Specifically, the goal will be to decide whether the value obtained is at least . Let a be some "large enough constant", and consider all inputs where the threshold has bitsize at most and each parameter generated from has bitsize at most .

This is a three-parameter system (d=3). We can therefore translate the structural result at the top of the post into a concrete statement regarding all problems parametrized in this manner.

Let be some constant. Set the desired time bound , and let the number of processors . Then a linear PRAM algorithm that works on this parametrized input in the specified resource bounds induces a partition of by at most planes, where each face can be labelled as specified above.

There's a more general version of this theorem that makes the tradeoff between time and processors more explicit: I'll skip that for now. Also note that the "5" in the exponent is somewhat arbitrary: it's just chosen to make things work unambiguously.

2. An affine transformation

We'll now encounter an ingenious geometric representation of the set of feasible inputs for the parametric problem. Let be the optimal function value as a function of the input P, and let G be its function graph. An input I to the problem is parametrized by the three parameters , and is feasible when , which can be restated (remembering that ) as the condition (dividing through by and using homogeneity. We will also assume wlog that is positive)

At this point, a geometer will look at expressions like , and immediately see a projective plane. And that's what happens ! We can think of the space of possible parameter values as inhabiting a projective space, with playing the role of the z-direction (in which case the action, as it were, happens on the z=1 plane).
The parameters define a ray in 3D that intersects the z=1 plane in the point (you should look at Figure 4.1 in the paper to help visualize what's going on).

What then happens to the function graph G ? We can think of G as lying in the affine plane z=1 (parametrized by ), and fan(G) as the set of all points in that project onto $G$ (via the projective transform). We can now translate the feasibility condition into the geometric condition that the point lies "below" fan(G) in the axis.

It helps to think of as an ordinary function in the affine plane, in which case the space of feasible values is the set of all points that project to points in the plane below its graph. In other words, all integer points in are labelled as 1 if they lie below fan(G) in the direction.

In the next installment, we'll show that any arrangement of few hyperplanes in this space will not be able to capture all the 0 and 1 points correctly.