YES(?,O(n^1))

Problem:
 f(0()) -> s(0())
 f(s(x)) -> g(s(s(x)))
 g(0()) -> s(0())
 g(s(0())) -> s(0())
 g(s(s(x))) -> f(x)

Proof:
 Matrix Interpretation Processor:
  dimension: 1
  interpretation:
   [g](x0) = x0 + 16,
   
   [s](x0) = x0 + 3,
   
   [f](x0) = x0 + 20,
   
   [0] = 29
  orientation:
   f(0()) = 49 >= 32 = s(0())
   
   f(s(x)) = x + 23 >= x + 22 = g(s(s(x)))
   
   g(0()) = 45 >= 32 = s(0())
   
   g(s(0())) = 48 >= 32 = s(0())
   
   g(s(s(x))) = x + 22 >= x + 20 = f(x)
  problem:
   
  Qed