YES(?,O(n^2)) 7.04/5.67 YES(?,O(n^2)) 7.04/5.67 7.04/5.67 Problem: 7.04/5.67 f(x,a()) -> x 7.04/5.67 f(x,g(y)) -> f(g(x),y) 7.04/5.67 7.04/5.67 Proof: 7.04/5.67 Complexity Transformation Processor: 7.04/5.67 strict: 7.04/5.67 f(x,a()) -> x 7.04/5.67 f(x,g(y)) -> f(g(x),y) 7.04/5.67 weak: 7.04/5.67 7.04/5.67 Matrix Interpretation Processor: dim=1 7.04/5.67 7.04/5.67 max_matrix: 7.04/5.67 1 7.04/5.67 interpretation: 7.04/5.67 [g](x0) = x0, 7.04/5.67 7.04/5.67 [f](x0, x1) = x0 + x1 + 240, 7.04/5.67 7.04/5.67 [a] = 32 7.04/5.67 orientation: 7.04/5.67 f(x,a()) = x + 272 >= x = x 7.04/5.67 7.04/5.67 f(x,g(y)) = x + y + 240 >= x + y + 240 = f(g(x),y) 7.04/5.67 problem: 7.04/5.67 strict: 7.04/5.67 f(x,g(y)) -> f(g(x),y) 7.04/5.67 weak: 7.04/5.67 f(x,a()) -> x 7.04/5.67 Matrix Interpretation Processor: dim=2 7.04/5.67 7.04/5.67 max_matrix: 7.04/5.67 [1 1] 7.04/5.67 [0 1] 7.04/5.67 interpretation: 7.04/5.67 [0] 7.04/5.67 [g](x0) = x0 + [1], 7.04/5.67 7.04/5.67 [1 1] 7.04/5.67 [f](x0, x1) = x0 + [0 1]x1, 7.04/5.67 7.04/5.67 [3] 7.04/5.67 [a] = [4] 7.04/5.67 orientation: 7.04/5.67 [1 1] [1] [1 1] [0] 7.04/5.67 f(x,g(y)) = x + [0 1]y + [1] >= x + [0 1]y + [1] = f(g(x),y) 7.04/5.67 7.04/5.67 [7] 7.04/5.67 f(x,a()) = x + [4] >= x = x 7.04/5.67 problem: 7.04/5.67 strict: 7.04/5.67 7.04/5.67 weak: 7.04/5.67 f(x,g(y)) -> f(g(x),y) 7.04/5.67 f(x,a()) -> x 7.04/5.67 Qed 7.04/5.67 EOF