YES(?,O(n^1)) 0.16/0.24 YES(?,O(n^1)) 0.16/0.24 0.16/0.24 Problem: 0.16/0.24 f(f(x)) -> g(f(x)) 0.16/0.24 g(g(x)) -> f(x) 0.16/0.24 0.16/0.24 Proof: 0.16/0.24 Complexity Transformation Processor: 0.16/0.24 strict: 0.16/0.24 f(f(x)) -> g(f(x)) 0.16/0.24 g(g(x)) -> f(x) 0.16/0.24 weak: 0.16/0.24 0.16/0.24 Matrix Interpretation Processor: dim=1 0.16/0.24 0.16/0.24 max_matrix: 0.16/0.24 1 0.16/0.24 interpretation: 0.16/0.24 [g](x0) = x0 + 32, 0.16/0.24 0.16/0.24 [f](x0) = x0 + 128 0.16/0.24 orientation: 0.16/0.24 f(f(x)) = x + 256 >= x + 160 = g(f(x)) 0.16/0.24 0.16/0.24 g(g(x)) = x + 64 >= x + 128 = f(x) 0.16/0.24 problem: 0.16/0.24 strict: 0.16/0.24 g(g(x)) -> f(x) 0.16/0.24 weak: 0.16/0.24 f(f(x)) -> g(f(x)) 0.16/0.24 Matrix Interpretation Processor: dim=1 0.16/0.24 0.16/0.24 max_matrix: 0.16/0.24 1 0.16/0.24 interpretation: 0.16/0.24 [g](x0) = x0 + 54, 0.16/0.24 0.16/0.24 [f](x0) = x0 + 96 0.16/0.24 orientation: 0.16/0.24 g(g(x)) = x + 108 >= x + 96 = f(x) 0.16/0.24 0.16/0.24 f(f(x)) = x + 192 >= x + 150 = g(f(x)) 0.16/0.24 problem: 0.16/0.24 strict: 0.16/0.24 0.16/0.24 weak: 0.16/0.24 g(g(x)) -> f(x) 0.16/0.24 f(f(x)) -> g(f(x)) 0.16/0.24 Qed 0.16/0.25 EOF