YES(?,O(n^1))

Problem:
 .(1(),x) -> x
 .(x,1()) -> x
 .(i(x),x) -> 1()
 .(x,i(x)) -> 1()
 i(1()) -> 1()
 i(i(x)) -> x
 .(i(y),.(y,z)) -> z
 .(y,.(i(y),z)) -> z

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