YES(?,O(n^1))
* Step 1: UnsatPaths WORST_CASE(?,O(n^1))
    + Considered Problem:
        Rules:
          0. eval1(A,B) -> eval2(A,B)           [A >= 1 && B = A]                          (?,1)
          1. eval2(A,B) -> eval2(-1 + A,-1 + B) [A + -1*B >= 0 && -1*A + B >= 0 && A >= 1] (?,1)
          2. eval2(A,B) -> eval1(A,B)           [A + -1*B >= 0 && -1*A + B >= 0 && 0 >= A] (?,1)
          3. start(A,B) -> eval1(A,B)           True                                       (1,1)
        Signature:
          {(eval1,2);(eval2,2);(start,2)}
        Flow Graph:
          [0->{1,2},1->{1,2},2->{0},3->{0}]
        
    + Applied Processor:
        UnsatPaths
    + Details:
        We remove following edges from the transition graph: [(0,2),(2,0)]
* Step 2: TrivialSCCs WORST_CASE(?,O(n^1))
    + Considered Problem:
        Rules:
          0. eval1(A,B) -> eval2(A,B)           [A >= 1 && B = A]                          (?,1)
          1. eval2(A,B) -> eval2(-1 + A,-1 + B) [A + -1*B >= 0 && -1*A + B >= 0 && A >= 1] (?,1)
          2. eval2(A,B) -> eval1(A,B)           [A + -1*B >= 0 && -1*A + B >= 0 && 0 >= A] (?,1)
          3. start(A,B) -> eval1(A,B)           True                                       (1,1)
        Signature:
          {(eval1,2);(eval2,2);(start,2)}
        Flow Graph:
          [0->{1},1->{1,2},2->{},3->{0}]
        
    + Applied Processor:
        TrivialSCCs
    + Details:
        All trivial SCCs of the transition graph admit timebound 1.
* Step 3: PolyRank WORST_CASE(?,O(n^1))
    + Considered Problem:
        Rules:
          0. eval1(A,B) -> eval2(A,B)           [A >= 1 && B = A]                          (1,1)
          1. eval2(A,B) -> eval2(-1 + A,-1 + B) [A + -1*B >= 0 && -1*A + B >= 0 && A >= 1] (?,1)
          2. eval2(A,B) -> eval1(A,B)           [A + -1*B >= 0 && -1*A + B >= 0 && 0 >= A] (1,1)
          3. start(A,B) -> eval1(A,B)           True                                       (1,1)
        Signature:
          {(eval1,2);(eval2,2);(start,2)}
        Flow Graph:
          [0->{1},1->{1,2},2->{},3->{0}]
        
    + Applied Processor:
        PolyRank {useFarkas = True, withSizebounds = [], shape = Linear}
    + Details:
        We apply a polynomial interpretation of shape linear:
          p(eval1) = x1
          p(eval2) = x1
          p(start) = x1
        
        Following rules are strictly oriented:
        [A + -1*B >= 0 && -1*A + B >= 0 && A >= 1] ==>                     
                                        eval2(A,B)   = A                   
                                                     > -1 + A              
                                                     = eval2(-1 + A,-1 + B)
        
        
        Following rules are weakly oriented:
                                 [A >= 1 && B = A] ==>           
                                        eval1(A,B)   = A         
                                                    >= A         
                                                     = eval2(A,B)
        
        [A + -1*B >= 0 && -1*A + B >= 0 && 0 >= A] ==>           
                                        eval2(A,B)   = A         
                                                    >= A         
                                                     = eval1(A,B)
        
                                              True ==>           
                                        start(A,B)   = A         
                                                    >= A         
                                                     = eval1(A,B)
        
        
* Step 4: KnowledgePropagation WORST_CASE(?,O(n^1))
    + Considered Problem:
        Rules:
          0. eval1(A,B) -> eval2(A,B)           [A >= 1 && B = A]                          (1,1)
          1. eval2(A,B) -> eval2(-1 + A,-1 + B) [A + -1*B >= 0 && -1*A + B >= 0 && A >= 1] (A,1)
          2. eval2(A,B) -> eval1(A,B)           [A + -1*B >= 0 && -1*A + B >= 0 && 0 >= A] (1,1)
          3. start(A,B) -> eval1(A,B)           True                                       (1,1)
        Signature:
          {(eval1,2);(eval2,2);(start,2)}
        Flow Graph:
          [0->{1},1->{1,2},2->{},3->{0}]
        
    + Applied Processor:
        KnowledgePropagation
    + Details:
        The problem is already solved.

YES(?,O(n^1))