Computational Complexity: Proceedings : Fifteenth Annual IEEE Conference on Computational Complexity : July 4-7, 2000, Florence, Italy |
From inside the book
Results 1-3 of 5
Page 38
... LBSP consisting of m instructions 11 , ... , Im can be viewed as a product of matrices A , .Am . Initial values of the registers are given as a row vector r = ( ni , ... , rw ) and executing a program means to multiply r on the right by ...
... LBSP consisting of m instructions 11 , ... , Im can be viewed as a product of matrices A , .Am . Initial values of the registers are given as a row vector r = ( ni , ... , rw ) and executing a program means to multiply r on the right by ...
Page 40
... LBSP Pjeling ) whose width is bounded by 2k + 2. Now we make use of the induction hypothesis and replace in every program Pje ( ing ) each instruction Rj + R ; ( R ; A yw ) by the program Pjeli'nhu ) . Altogether , we have constructed ...
... LBSP Pjeling ) whose width is bounded by 2k + 2. Now we make use of the induction hypothesis and replace in every program Pje ( ing ) each instruction Rj + R ; ( R ; A yw ) by the program Pjeli'nhu ) . Altogether , we have constructed ...
Page 41
... LBSP over the ring Z2 ( { 0 , 1 } , 0,1,0,1 ) of width w , that computes a function f E Bn and contains r variable references , is simulated by a PBP of length max { r , 1 } and width 2 " . Proof . Let { x1 , ... , xn } be the set of ...
... LBSP over the ring Z2 ( { 0 , 1 } , 0,1,0,1 ) of width w , that computes a function f E Bn and contains r variable references , is simulated by a PBP of length max { r , 1 } and width 2 " . Proof . Let { x1 , ... , xn } be the set of ...
Contents
A Lower Bound for the Shortest Path Problem | 14 |
TimeSpace Lower Bounds for SAT on Uniform and NonUniform Machines | 22 |
BP f 0 L l+E | 36 |
Copyright | |
23 other sections not shown
Other editions - View all
Common terms and phrases
accepts addition algebraic algorithm apply arbitrary assume bits Boolean called circuit classical colors complexity computation Computer Science condition consider constant construct contains Corollary corresponding defined definition denote depth determine deterministic edges elements equal equivalent example exists fact finite fixed formula function gates give given graph hard Hence holds IEEE implies induction input integer known Kolmogorov language least Lemma length linear logspace lower bounds matrix multiplication natural node nondeterministic Note O(log obtain operations optimal output path polynomial positive possible probability problem proof prove quantum query random reduction respectively result running satisfiability similar simulation space step string takes tape tensor formula Theorem Theory tion tree Turing machine University variables vector vertices weight