YES(?,O(n^2)) Problem: w(r(x)) -> r(w(x)) b(r(x)) -> r(b(x)) b(w(x)) -> w(b(x)) Proof: Complexity Transformation Processor: strict: w(r(x)) -> r(w(x)) b(r(x)) -> r(b(x)) b(w(x)) -> w(b(x)) weak: Matrix Interpretation Processor: dimension: 2 max_matrix: [1 1] [0 1] interpretation: [1 1] [b](x0) = [0 1]x0, [1] [w](x0) = x0 + [0], [0] [r](x0) = x0 + [1] orientation: [1] [1] w(r(x)) = x + [1] >= x + [1] = r(w(x)) [1 1] [1] [1 1] [0] b(r(x)) = [0 1]x + [1] >= [0 1]x + [1] = r(b(x)) [1 1] [1] [1 1] [1] b(w(x)) = [0 1]x + [0] >= [0 1]x + [0] = w(b(x)) problem: strict: w(r(x)) -> r(w(x)) b(w(x)) -> w(b(x)) weak: b(r(x)) -> r(b(x)) Matrix Interpretation Processor: dimension: 2 max_matrix: [1 1] [0 1] interpretation: [1 1] [0] [b](x0) = [0 1]x0 + [1], [0] [w](x0) = x0 + [1], [1] [r](x0) = x0 + [1] orientation: [1] [1] w(r(x)) = x + [2] >= x + [2] = r(w(x)) [1 1] [1] [1 1] [0] b(w(x)) = [0 1]x + [2] >= [0 1]x + [2] = w(b(x)) [1 1] [2] [1 1] [1] b(r(x)) = [0 1]x + [2] >= [0 1]x + [2] = r(b(x)) problem: strict: w(r(x)) -> r(w(x)) weak: b(w(x)) -> w(b(x)) b(r(x)) -> r(b(x)) Matrix Interpretation Processor: dimension: 2 max_matrix: [1 1] [0 1] interpretation: [b](x0) = x0, [1 1] [w](x0) = [0 1]x0, [1] [r](x0) = x0 + [1] orientation: [1 1] [2] [1 1] [1] w(r(x)) = [0 1]x + [1] >= [0 1]x + [1] = r(w(x)) [1 1] [1 1] b(w(x)) = [0 1]x >= [0 1]x = w(b(x)) [1] [1] b(r(x)) = x + [1] >= x + [1] = r(b(x)) problem: strict: weak: w(r(x)) -> r(w(x)) b(w(x)) -> w(b(x)) b(r(x)) -> r(b(x)) Qed