YES
Input TRS:
      1: empty(nil()) -> true()
      2: empty(cons(x,y)) -> false()
      3: tail(nil()) -> nil()
      4: tail(cons(x,y)) -> y
      5: head(cons(x,y)) -> x
      6: zero(0()) -> true()
      7: zero(s(x)) -> false()
      8: p(0()) -> 0()
      9: p(s(0())) -> 0()
      10: p(s(s(x))) -> s(p(s(x)))
      11: intlist(x) -> if_intlist(empty(x),x)
      12: if_intlist(true(),x) -> nil()
      13: if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
      14: int(x,y) -> if_int(zero(x),zero(y),x,y)
      15: if_int(true(),b,x,y) -> if1(b,x,y)
      16: if_int(false(),b,x,y) -> if2(b,x,y)
      17: if1(true(),x,y) -> cons(0(),nil())
      18: if1(false(),x,y) -> cons(0(),int(s(0()),y))
      19: if2(true(),x,y) -> nil()
      20: if2(false(),x,y) -> intlist(int(p(x),p(y)))
Number of strict rules: 20
Direct POLO(bPol) ... failed.
Uncurrying p
      1: empty(nil()) -> true()
      2: empty(cons(x,y)) -> false()
      3: tail(nil()) -> nil()
      4: tail(cons(x,y)) -> y
      5: head(cons(x,y)) -> x
      6: zero(0()) -> true()
      7: zero(s(x)) -> false()
      8: p^1_0() -> 0()
      9: p^1_s(0()) -> 0()
      10: p^1_s(s(x)) -> s(p^1_s(x))
      11: intlist(x) -> if_intlist(empty(x),x)
      12: if_intlist(true(),x) -> nil()
      13: if_intlist(false(),x) -> cons(s(head(x)),intlist(tail(x)))
      14: int(x,y) -> if_int(zero(x),zero(y),x,y)
      15: if_int(true(),b,x,y) -> if1(b,x,y)
      16: if_int(false(),b,x,y) -> if2(b,x,y)
      17: if1(true(),x,y) -> cons(0(),nil())
      18: if1(false(),x,y) -> cons(0(),int(s(0()),y))
      19: if2(true(),x,y) -> nil()
      20: if2(false(),x,y) -> intlist(int(p(x),p(y)))
      21: p(0()) ->= p^1_0()
      22: p(s(_1)) ->= p^1_s(_1)
Number of strict rules: 20
Direct POLO(bPol) ... failed.
Dependency Pairs:
     #1: #if_intlist(false(),x) -> #head(x)
     #2: #if_intlist(false(),x) -> #intlist(tail(x))
     #3: #if_intlist(false(),x) -> #tail(x)
     #4: #intlist(x) -> #if_intlist(empty(x),x)
     #5: #intlist(x) -> #empty(x)
     #6: #int(x,y) -> #if_int(zero(x),zero(y),x,y)
     #7: #int(x,y) -> #zero(x)
     #8: #int(x,y) -> #zero(y)
     #9: #if2(false(),x,y) -> #intlist(int(p(x),p(y)))
     #10: #if2(false(),x,y) -> #int(p(x),p(y))
     #11: #if2(false(),x,y) -> #p(x)
     #12: #if2(false(),x,y) -> #p(y)
     #13: #p^1_s(s(x)) -> #p^1_s(x)
     #14: #p(s(_1)) ->? #p^1_s(_1)
     #15: #p(0()) ->? #p^1_0()
     #16: #if_int(false(),b,x,y) -> #if2(b,x,y)
     #17: #if_int(true(),b,x,y) -> #if1(b,x,y)
     #18: #if1(false(),x,y) -> #int(s(0()),y)
Number of SCCs: 3, DPs: 8
  SCC { #13 }
POLO(Sum)... succeeded.
      zero	w: 0
      #empty	w: 0
      #intlist	w: 0
      s 	w: x1 + 1
      #p^1_0	w: 0
      if_int	w: 0
      #p^1_s	w: x1
      #if_int	w: 0
      p^1_0	w: 0
      if1	w: 0
      false	w: 0
      #head	w: 0
      p^1_s	w: 0
      #p 	w: 0
      true	w: 0
      #if1	w: 0
      if2	w: 0
      p 	w: 0
      tail	w: 0
      0 	w: 0
      nil	w: 0
      intlist	w: 0
      #tail	w: 0
      #if_intlist	w: 0
      int	w: 0
      head	w: 0
      cons	w: 0
      empty	w: 0
      #zero	w: 0
      #if2	w: 0
      if_intlist	w: 0
      #int	w: 0
    USABLE RULES: { }
    Removed DPs: #13
Number of SCCs: 2, DPs: 7
  SCC { #2 #4 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... succeeded.
      zero	w: 0
      #empty	w: max(x1 - 1, 0)
      #intlist	w: max(x1 + 1, 0)
      s 	w: 0
      #p^1_0	w: 0
      if_int	w: max(x3 - 1, 0)
      #p^1_s	w: max(x1 - 1, 0)
      #if_int	w: 0
      p^1_0	w: 0
      if1	w: max(x2 - 1, 0)
      false	w: 2
      #head	w: 0
      p^1_s	w: max(x1 - 1, 0)
      #p 	w: max(x1 - 1, 0)
      true	w: 0
      #if1	w: 0
      if2	w: max(x2 - 1, 0)
      p 	w: max(x1 - 1, 0)
      tail	w: max(x1 - 2, 0)
      0 	w: 0
      nil	w: 0
      intlist	w: max(x1 - 1, 0)
      #tail	w: 0
      #if_intlist	w: max(x1 - 1, x2 - 1, 0)
      int	w: 0
      head	w: max(x1 - 1, 0)
      cons	w: max(x2 + 3, 0)
      empty	w: max(x1 - 1, 0)
      #zero	w: 0
      #if2	w: 0
      if_intlist	w: max(x1 - 1, 0)
      #int	w: 0
    USABLE RULES: { 1..4 }
    Removed DPs: #4
Number of SCCs: 1, DPs: 5
  SCC { #6 #10 #16..18 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... succeeded.
      zero	w: max(x1 + 3, 0)
      #empty	w: max(x1 - 1, 0)
      #intlist	w: max(x1 + 1, 0)
      s 	w: max(x1 + 4, 0)
      #p^1_0	w: 0
      if_int	w: max(x3 - 1, 0)
      #p^1_s	w: max(x1 - 1, 0)
      #if_int	w: max(x2 - 5, x3 - 4, x4 - 1, 0)
      p^1_0	w: 0
      if1	w: max(x2 - 1, 0)
      false	w: 6
      #head	w: 0
      p^1_s	w: max(x1 + 1, 0)
      #p 	w: max(x1 - 1, 0)
      true	w: 2
      #if1	w: max(x1 - 5, x2 - 4, x3 - 1, 0)
      if2	w: max(x2 - 1, 0)
      p 	w: max(x1 - 2, 0)
      tail	w: max(x1 - 2, 0)
      0 	w: 0
      nil	w: 0
      intlist	w: max(x1 - 1, 0)
      #tail	w: 0
      #if_intlist	w: max(x1, 0)
      int	w: 0
      head	w: max(x1 - 1, 0)
      cons	w: max(x2 + 5, 0)
      empty	w: max(x1 + 2, 0)
      #zero	w: 0
      #if2	w: max(x1 - 5, x2 - 4, x3 - 1, 0)
      if_intlist	w: max(x1 - 1, 0)
      #int	w: max(x1 - 3, x2 - 1, 0)
    USABLE RULES: { 1..4 6..10 21 22 }
    Removed DPs: #10
Number of SCCs: 1, DPs: 3
  SCC { #6 #17 #18 }
POLO(Sum)... succeeded.
      zero	w: x1 + 1
      #empty	w: 0
      #intlist	w: 0
      s 	w: 1
      #p^1_0	w: 0
      if_int	w: 0
      #p^1_s	w: 0
      #if_int	w: x1
      p^1_0	w: 4
      if1	w: 0
      false	w: 1
      #head	w: 0
      p^1_s	w: 4
      #p 	w: 0
      true	w: 5
      #if1	w: 4
      if2	w: 0
      p 	w: 4
      tail	w: 0
      0 	w: 4
      nil	w: 1
      intlist	w: 0
      #tail	w: 0
      #if_intlist	w: 0
      int	w: 0
      head	w: 0
      cons	w: 1
      empty	w: 0
      #zero	w: 0
      #if2	w: 4
      if_intlist	w: 0
      #int	w: x1 + 2
    USABLE RULES: { 6..10 21 22 }
    Removed DPs: #6 #17 #18
Number of SCCs: 0, DPs: 0