YES(?,O(n^1))

Problem:
 R(x1) -> r(x1)
 r(p(x1)) -> p(p(r(P(x1))))
 r(r(x1)) -> x1
 r(P(P(x1))) -> P(P(r(x1)))
 p(P(x1)) -> x1
 P(p(x1)) -> x1
 r(R(x1)) -> x1
 R(r(x1)) -> x1

Proof:
 Bounds Processor:
  bound: 1
  enrichment: match
  automaton:
   final states: {5,4,3,2}
   transitions:
    r1(6) -> 7*
    R0(1) -> 2*
    r0(1) -> 3*
    p0(1) -> 4*
    P0(1) -> 5*
    f80() -> 1*
    1 -> 6*
    7 -> 2*
  problem:
   
  Qed