论文标题
代数机器的下限，语义上
Lower bounds for algebraic machines, semantically
论文作者
论文摘要
本文提出了一种新的语义方法，用于证明计算复杂性的下限。我们用它来证明，PimeT完全问题MaxFlow在平行的随机访问机上（PRAMS）在与整数合作的Polyrogarithmic时间中不可计算，这表明NCZ \ neq ptime是NCZ是由此类机器定义的复杂性类别，P Time是ptime，P Time是可计算的标准类别计算的问题（on Machine，a turn Machine）。除了显示这种新的分离结果外，我们显示了我们的方法捕获了以前的下限结果：Steele和Yao的代数决策树的下限，Ben-OR代数计算树的下限，Cucker的NC证明了NC的NC证明NC不等于Reals上的P Time，以及Mulmuley的下限，而Mulmuley的下限则无需使用“ Prams”。
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".
