YES(?,O(n^2)) 8.39/5.83 YES(?,O(n^2)) 8.39/5.83 8.39/5.83 Problem: 8.39/5.83 g(f(x),y) -> f(h(x,y)) 8.39/5.83 h(x,y) -> g(x,f(y)) 8.39/5.83 8.39/5.83 Proof: 8.39/5.83 Complexity Transformation Processor: 8.39/5.83 strict: 8.39/5.83 g(f(x),y) -> f(h(x,y)) 8.39/5.83 h(x,y) -> g(x,f(y)) 8.39/5.83 weak: 8.39/5.83 8.39/5.83 Matrix Interpretation Processor: dim=1 8.39/5.83 8.39/5.83 max_matrix: 8.39/5.83 1 8.39/5.83 interpretation: 8.39/5.83 [h](x0, x1) = x0 + x1 + 237, 8.39/5.83 8.39/5.83 [g](x0, x1) = x0 + x1 + 76, 8.39/5.83 8.39/5.83 [f](x0) = x0 + 64 8.39/5.83 orientation: 8.39/5.83 g(f(x),y) = x + y + 140 >= x + y + 301 = f(h(x,y)) 8.39/5.83 8.39/5.83 h(x,y) = x + y + 237 >= x + y + 140 = g(x,f(y)) 8.39/5.83 problem: 8.39/5.83 strict: 8.39/5.83 g(f(x),y) -> f(h(x,y)) 8.39/5.83 weak: 8.39/5.83 h(x,y) -> g(x,f(y)) 8.39/5.83 Matrix Interpretation Processor: dim=2 8.39/5.83 8.39/5.83 max_matrix: 8.39/5.83 [1 2] 8.39/5.83 [0 1] 8.39/5.83 interpretation: 8.39/5.83 [1 2] [1 0] 8.39/5.83 [h](x0, x1) = [0 1]x0 + [0 0]x1, 8.39/5.83 8.39/5.83 [1 2] [1 0] 8.39/5.83 [g](x0, x1) = [0 1]x0 + [0 0]x1, 8.39/5.83 8.39/5.83 [0] 8.39/5.83 [f](x0) = x0 + [5] 8.39/5.83 orientation: 8.39/5.83 [1 2] [1 0] [10] [1 2] [1 0] [0] 8.39/5.83 g(f(x),y) = [0 1]x + [0 0]y + [5 ] >= [0 1]x + [0 0]y + [5] = f(h(x,y)) 8.39/5.83 8.39/5.83 [1 2] [1 0] [1 2] [1 0] 8.39/5.83 h(x,y) = [0 1]x + [0 0]y >= [0 1]x + [0 0]y = g(x,f(y)) 8.39/5.83 problem: 8.39/5.83 strict: 8.39/5.83 8.39/5.83 weak: 8.39/5.83 g(f(x),y) -> f(h(x,y)) 8.39/5.83 h(x,y) -> g(x,f(y)) 8.39/5.83 Qed 8.39/5.83 EOF