YES

Problem:
 fib(0()) -> 0()
 fib(s(0())) -> s(0())
 fib(s(s(x))) -> +(fib(s(x)),fib(x))

Proof:
 DP Processor:
  DPs:
   fib#(s(s(x))) -> fib#(x)
   fib#(s(s(x))) -> fib#(s(x))
  TRS:
   fib(0()) -> 0()
   fib(s(0())) -> s(0())
   fib(s(s(x))) -> +(fib(s(x)),fib(x))
  Usable Rule Processor:
   DPs:
    fib#(s(s(x))) -> fib#(x)
    fib#(s(s(x))) -> fib#(s(x))
   TRS:
    
   Arctic Interpretation Processor:
    dimension: 1
    usable rules:
     
    interpretation:
     [fib#](x0) = x0,
     
     [s](x0) = 2x0 + -6
    orientation:
     fib#(s(s(x))) = 4x + -4 >= x = fib#(x)
     
     fib#(s(s(x))) = 4x + -4 >= 2x + -6 = fib#(s(x))
    problem:
     DPs:
      
     TRS:
      
    Qed