YES(?,O(n^2))

Problem:
 s(a()) -> a()
 s(s(x)) -> x
 s(f(x,y)) -> f(s(y),s(x))
 s(g(x,y)) -> g(s(x),s(y))
 f(x,a()) -> x
 f(a(),y) -> y
 f(g(x,y),g(u,v)) -> g(f(x,u),f(y,v))
 g(a(),a()) -> a()

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