YES(?,O(n^1))

Problem:
 P(x1) -> Q(Q(p(x1)))
 p(p(x1)) -> q(q(x1))
 p(Q(Q(x1))) -> Q(Q(p(x1)))
 Q(p(q(x1))) -> q(p(Q(x1)))
 q(q(p(x1))) -> p(q(q(x1)))
 q(Q(x1)) -> x1
 Q(q(x1)) -> x1
 p(P(x1)) -> x1
 P(p(x1)) -> x1

Proof:
 Bounds Processor:
  bound: 1
  enrichment: match
  automaton:
   final states: {5,4,3,2}
   transitions:
    Q1(7) -> 8*
    Q1(8) -> 9*
    p1(6) -> 7*
    P0(1) -> 2*
    Q0(1) -> 4*
    p0(1) -> 3*
    q0(1) -> 5*
    f80() -> 1*
    1 -> 6*
    9 -> 2*
  problem:
   
  Qed