  This paper presents a new semantic method for proving lower bounds in
computational complexity. We use it to prove that maxflow, a PTIME complete
problem, is not computable in polylogarithmic time on parallel random access
machines (PRAMs) working with integers, showing that NCZ \neq PTIME, where NCZ
is the complexity class defined by such machines, and PTIME is the standard
class of polynomial time computable problems (on, say, a Turing machine). On
top of showing this new separation result, we show our method captures previous
lower bounds results from the literature: Steele and Yao's lower bounds for
algebraic decision trees, Ben-Or's lower bounds for algebraic computation
trees, Cucker's proof that NC is not equal to PTIME on the reals, and
Mulmuley's lower bounds for "PRAMs without bit operations".
