YES(?,O(n^2))

Problem:
 g(f(x,y),z) -> f(x,g(y,z))
 g(h(x,y),z) -> g(x,f(y,z))
 g(x,h(y,z)) -> h(g(x,y),z)

Proof:
 Complexity Transformation Processor:
  strict:
   g(f(x,y),z) -> f(x,g(y,z))
   g(h(x,y),z) -> g(x,f(y,z))
   g(x,h(y,z)) -> h(g(x,y),z)
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   max_matrix:
    1
    interpretation:
     [h](x0, x1) = x0 + x1 + 1,
     
     [g](x0, x1) = x0 + x1,
     
     [f](x0, x1) = x0 + x1
    orientation:
     g(f(x,y),z) = x + y + z >= x + y + z = f(x,g(y,z))
     
     g(h(x,y),z) = x + y + z + 1 >= x + y + z = g(x,f(y,z))
     
     g(x,h(y,z)) = x + y + z + 1 >= x + y + z + 1 = h(g(x,y),z)
    problem:
     strict:
      g(f(x,y),z) -> f(x,g(y,z))
      g(x,h(y,z)) -> h(g(x,y),z)
     weak:
      g(h(x,y),z) -> g(x,f(y,z))
    Matrix Interpretation Processor:
     dimension: 2
     max_matrix:
      [1 1]
      [0 1]
      interpretation:
                          [1 0]     [0]
       [h](x0, x1) = x0 + [0 0]x1 + [1],
       
                     [1 0]     [1 1]  
       [g](x0, x1) = [0 0]x0 + [0 1]x1,
       
                     [1 0]       
       [f](x0, x1) = [0 0]x0 + x1
      orientation:
                     [1 0]    [1 0]    [1 1]     [1 0]    [1 0]    [1 1]               
       g(f(x,y),z) = [0 0]x + [0 0]y + [0 1]z >= [0 0]x + [0 0]y + [0 1]z = f(x,g(y,z))
       
                     [1 0]    [1 1]    [1 0]    [1]    [1 0]    [1 1]    [1 0]    [0]              
       g(x,h(y,z)) = [0 0]x + [0 1]y + [0 0]z + [1] >= [0 0]x + [0 1]y + [0 0]z + [1] = h(g(x,y),z)
       
                     [1 0]    [1 0]    [1 1]     [1 0]    [1 0]    [1 1]               
       g(h(x,y),z) = [0 0]x + [0 0]y + [0 1]z >= [0 0]x + [0 0]y + [0 1]z = g(x,f(y,z))
      problem:
       strict:
        g(f(x,y),z) -> f(x,g(y,z))
       weak:
        g(x,h(y,z)) -> h(g(x,y),z)
        g(h(x,y),z) -> g(x,f(y,z))
      Matrix Interpretation Processor:
       dimension: 2
       max_matrix:
        [1 1]
        [0 1]
        interpretation:
                            [1 0]     [0]
         [h](x0, x1) = x0 + [0 0]x1 + [1],
         
                       [1 1]       
         [g](x0, x1) = [0 1]x0 + x1,
         
                       [1 0]          [1]
         [f](x0, x1) = [0 0]x0 + x1 + [1]
        orientation:
                       [1 0]    [1 1]        [2]    [1 0]    [1 1]        [1]              
         g(f(x,y),z) = [0 0]x + [0 1]y + z + [1] >= [0 0]x + [0 1]y + z + [1] = f(x,g(y,z))
         
                       [1 1]        [1 0]    [0]    [1 1]        [1 0]    [0]              
         g(x,h(y,z)) = [0 1]x + y + [0 0]z + [1] >= [0 1]x + y + [0 0]z + [1] = h(g(x,y),z)
         
                       [1 1]    [1 0]        [1]    [1 1]    [1 0]        [1]              
         g(h(x,y),z) = [0 1]x + [0 0]y + z + [1] >= [0 1]x + [0 0]y + z + [1] = g(x,f(y,z))
        problem:
         strict:
          
         weak:
          g(f(x,y),z) -> f(x,g(y,z))
          g(x,h(y,z)) -> h(g(x,y),z)
          g(h(x,y),z) -> g(x,f(y,z))
        Qed