4.35/2.42 WORST_CASE(NON_POLY, ?) 4.35/2.43 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 4.35/2.43 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.35/2.43 4.35/2.43 4.35/2.43 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(EXP, EXP). 4.35/2.43 4.35/2.43 (0) CpxIntTrs 4.35/2.43 (1) Koat Proof [FINISHED, 128 ms] 4.35/2.43 (2) BOUNDS(1, EXP) 4.35/2.43 (3) Loat Proof [FINISHED, 326 ms] 4.35/2.43 (4) BOUNDS(EXP, INF) 4.35/2.43 4.35/2.43 4.35/2.43 ---------------------------------------- 4.35/2.43 4.35/2.43 (0) 4.35/2.43 Obligation: 4.35/2.43 Complexity Int TRS consisting of the following rules: 4.35/2.43 f(A, B, C) -> Com_1(g(1, 1, C)) :|: TRUE 4.35/2.43 g(A, B, C) -> Com_1(g(A + B, A + B, C - 1)) :|: C > 0 4.35/2.43 g(A, B, C) -> Com_1(h(A, B, C)) :|: C <= 0 4.35/2.43 h(A, B, C) -> Com_1(h(A, B - 1, C)) :|: B > 0 4.35/2.43 4.35/2.43 The start-symbols are:[f_3] 4.35/2.43 4.35/2.43 4.35/2.43 ---------------------------------------- 4.35/2.43 4.35/2.43 (1) Koat Proof (FINISHED) 4.35/2.43 YES(?, pow(2, 2*ar_2) + ar_2 + 3) 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Initial complexity problem: 4.35/2.43 4.35/2.43 1: T: 4.35/2.43 4.35/2.43 (Comp: ?, Cost: 1) f(ar_0, ar_1, ar_2) -> Com_1(g(1, 1, ar_2)) 4.35/2.43 4.35/2.43 (Comp: ?, Cost: 1) g(ar_0, ar_1, ar_2) -> Com_1(g(ar_0 + ar_1, ar_0 + ar_1, ar_2 - 1)) [ ar_2 >= 1 ] 4.35/2.43 4.35/2.43 (Comp: ?, Cost: 1) g(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 4.35/2.43 4.35/2.43 (Comp: ?, Cost: 1) h(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1 - 1, ar_2)) [ ar_1 >= 1 ] 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 4.35/2.43 4.35/2.43 start location: koat_start 4.35/2.43 4.35/2.43 leaf cost: 0 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Repeatedly propagating knowledge in problem 1 produces the following problem: 4.35/2.43 4.35/2.43 2: T: 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 1) f(ar_0, ar_1, ar_2) -> Com_1(g(1, 1, ar_2)) 4.35/2.43 4.35/2.43 (Comp: ?, Cost: 1) g(ar_0, ar_1, ar_2) -> Com_1(g(ar_0 + ar_1, ar_0 + ar_1, ar_2 - 1)) [ ar_2 >= 1 ] 4.35/2.43 4.35/2.43 (Comp: ?, Cost: 1) g(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 4.35/2.43 4.35/2.43 (Comp: ?, Cost: 1) h(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1 - 1, ar_2)) [ ar_1 >= 1 ] 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 4.35/2.43 4.35/2.43 start location: koat_start 4.35/2.43 4.35/2.43 leaf cost: 0 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 A polynomial rank function with 4.35/2.43 4.35/2.43 Pol(f) = 1 4.35/2.43 4.35/2.43 Pol(g) = 1 4.35/2.43 4.35/2.43 Pol(h) = 0 4.35/2.43 4.35/2.43 Pol(koat_start) = 1 4.35/2.43 4.35/2.43 orients all transitions weakly and the transition 4.35/2.43 4.35/2.43 g(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 4.35/2.43 4.35/2.43 strictly and produces the following problem: 4.35/2.43 4.35/2.43 3: T: 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 1) f(ar_0, ar_1, ar_2) -> Com_1(g(1, 1, ar_2)) 4.35/2.43 4.35/2.43 (Comp: ?, Cost: 1) g(ar_0, ar_1, ar_2) -> Com_1(g(ar_0 + ar_1, ar_0 + ar_1, ar_2 - 1)) [ ar_2 >= 1 ] 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 1) g(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 4.35/2.43 4.35/2.43 (Comp: ?, Cost: 1) h(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1 - 1, ar_2)) [ ar_1 >= 1 ] 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 4.35/2.43 4.35/2.43 start location: koat_start 4.35/2.43 4.35/2.43 leaf cost: 0 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 A polynomial rank function with 4.35/2.43 4.35/2.43 Pol(f) = V_3 4.35/2.43 4.35/2.43 Pol(g) = V_3 4.35/2.43 4.35/2.43 Pol(h) = V_3 4.35/2.43 4.35/2.43 Pol(koat_start) = V_3 4.35/2.43 4.35/2.43 orients all transitions weakly and the transition 4.35/2.43 4.35/2.43 g(ar_0, ar_1, ar_2) -> Com_1(g(ar_0 + ar_1, ar_0 + ar_1, ar_2 - 1)) [ ar_2 >= 1 ] 4.35/2.43 4.35/2.43 strictly and produces the following problem: 4.35/2.43 4.35/2.43 4: T: 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 1) f(ar_0, ar_1, ar_2) -> Com_1(g(1, 1, ar_2)) 4.35/2.43 4.35/2.43 (Comp: ar_2, Cost: 1) g(ar_0, ar_1, ar_2) -> Com_1(g(ar_0 + ar_1, ar_0 + ar_1, ar_2 - 1)) [ ar_2 >= 1 ] 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 1) g(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 4.35/2.43 4.35/2.43 (Comp: ?, Cost: 1) h(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1 - 1, ar_2)) [ ar_1 >= 1 ] 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 4.35/2.43 4.35/2.43 start location: koat_start 4.35/2.43 4.35/2.43 leaf cost: 0 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 A polynomial rank function with 4.35/2.43 4.35/2.43 Pol(h) = V_2 4.35/2.43 4.35/2.43 and size complexities 4.35/2.43 4.35/2.43 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(f(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-0) = ar_0 4.35/2.43 4.35/2.43 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(f(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-1) = ar_1 4.35/2.43 4.35/2.43 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(f(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-2) = ar_2 4.35/2.43 4.35/2.43 S("h(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1 - 1, ar_2)) [ ar_1 >= 1 ]", 0-0) = pow(2, 2*ar_2) + 1 4.35/2.43 4.35/2.43 S("h(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1 - 1, ar_2)) [ ar_1 >= 1 ]", 0-1) = pow(2, 2*ar_2) + 1 4.35/2.43 4.35/2.43 S("h(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1 - 1, ar_2)) [ ar_1 >= 1 ]", 0-2) = ar_2 4.35/2.43 4.35/2.43 S("g(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-0) = pow(2, 2*ar_2) + 1 4.35/2.43 4.35/2.43 S("g(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-1) = pow(2, 2*ar_2) + 1 4.35/2.43 4.35/2.43 S("g(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-2) = ar_2 4.35/2.43 4.35/2.43 S("g(ar_0, ar_1, ar_2) -> Com_1(g(ar_0 + ar_1, ar_0 + ar_1, ar_2 - 1)) [ ar_2 >= 1 ]", 0-0) = pow(2, 2*ar_2) 4.35/2.43 4.35/2.43 S("g(ar_0, ar_1, ar_2) -> Com_1(g(ar_0 + ar_1, ar_0 + ar_1, ar_2 - 1)) [ ar_2 >= 1 ]", 0-1) = pow(2, 2*ar_2) 4.35/2.43 4.35/2.43 S("g(ar_0, ar_1, ar_2) -> Com_1(g(ar_0 + ar_1, ar_0 + ar_1, ar_2 - 1)) [ ar_2 >= 1 ]", 0-2) = ar_2 4.35/2.43 4.35/2.43 S("f(ar_0, ar_1, ar_2) -> Com_1(g(1, 1, ar_2))", 0-0) = 1 4.35/2.43 4.35/2.43 S("f(ar_0, ar_1, ar_2) -> Com_1(g(1, 1, ar_2))", 0-1) = 1 4.35/2.43 4.35/2.43 S("f(ar_0, ar_1, ar_2) -> Com_1(g(1, 1, ar_2))", 0-2) = ar_2 4.35/2.43 4.35/2.43 orients the transitions 4.35/2.43 4.35/2.43 h(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1 - 1, ar_2)) [ ar_1 >= 1 ] 4.35/2.43 4.35/2.43 weakly and the transition 4.35/2.43 4.35/2.43 h(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1 - 1, ar_2)) [ ar_1 >= 1 ] 4.35/2.43 4.35/2.43 strictly and produces the following problem: 4.35/2.43 4.35/2.43 5: T: 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 1) f(ar_0, ar_1, ar_2) -> Com_1(g(1, 1, ar_2)) 4.35/2.43 4.35/2.43 (Comp: ar_2, Cost: 1) g(ar_0, ar_1, ar_2) -> Com_1(g(ar_0 + ar_1, ar_0 + ar_1, ar_2 - 1)) [ ar_2 >= 1 ] 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 1) g(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 4.35/2.43 4.35/2.43 (Comp: pow(2, 2*ar_2) + 1, Cost: 1) h(ar_0, ar_1, ar_2) -> Com_1(h(ar_0, ar_1 - 1, ar_2)) [ ar_1 >= 1 ] 4.35/2.43 4.35/2.43 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 4.35/2.43 4.35/2.43 start location: koat_start 4.35/2.43 4.35/2.43 leaf cost: 0 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Complexity upper bound pow(2, 2*ar_2) + ar_2 + 3 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Time: 0.136 sec (SMT: 0.129 sec) 4.35/2.43 4.35/2.43 4.35/2.43 ---------------------------------------- 4.35/2.43 4.35/2.43 (2) 4.35/2.43 BOUNDS(1, EXP) 4.35/2.43 4.35/2.43 ---------------------------------------- 4.35/2.43 4.35/2.43 (3) Loat Proof (FINISHED) 4.35/2.43 4.35/2.43 4.35/2.43 ### Pre-processing the ITS problem ### 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Initial linear ITS problem 4.35/2.43 4.35/2.43 Start location: f 4.35/2.43 4.35/2.43 0: f -> g : A'=1, B'=1, [], cost: 1 4.35/2.43 4.35/2.43 1: g -> g : A'=A+B, B'=A+B, C'=-1+C, [ C>=1 ], cost: 1 4.35/2.43 4.35/2.43 2: g -> h : [ 0>=C ], cost: 1 4.35/2.43 4.35/2.43 3: h -> h : B'=-1+B, [ B>=1 ], cost: 1 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 ### Simplification by acceleration and chaining ### 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Accelerating simple loops of location 1. 4.35/2.43 4.35/2.43 Accelerating the following rules: 4.35/2.43 4.35/2.43 1: g -> g : A'=A+B, B'=A+B, C'=-1+C, [ C>=1 ], cost: 1 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Accelerated rule 1 with metering function C, yielding the new rule 4. 4.35/2.43 4.35/2.43 Removing the simple loops: 1. 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Accelerating simple loops of location 2. 4.35/2.43 4.35/2.43 Accelerating the following rules: 4.35/2.43 4.35/2.43 3: h -> h : B'=-1+B, [ B>=1 ], cost: 1 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Accelerated rule 3 with metering function B, yielding the new rule 5. 4.35/2.43 4.35/2.43 Removing the simple loops: 3. 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Accelerated all simple loops using metering functions (where possible): 4.35/2.43 4.35/2.43 Start location: f 4.35/2.43 4.35/2.43 0: f -> g : A'=1, B'=1, [], cost: 1 4.35/2.43 4.35/2.43 2: g -> h : [ 0>=C ], cost: 1 4.35/2.43 4.35/2.43 4: g -> g : A'=2^C*A, B'=2^C*A, C'=0, [ C>=1 && B==A ], cost: C 4.35/2.43 4.35/2.43 5: h -> h : B'=0, [ B>=1 ], cost: B 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Chained accelerated rules (with incoming rules): 4.35/2.43 4.35/2.43 Start location: f 4.35/2.43 4.35/2.43 0: f -> g : A'=1, B'=1, [], cost: 1 4.35/2.43 4.35/2.43 6: f -> g : A'=2^C, B'=2^C, C'=0, [ C>=1 ], cost: 1+C 4.35/2.43 4.35/2.43 2: g -> h : [ 0>=C ], cost: 1 4.35/2.43 4.35/2.43 7: g -> h : B'=0, [ 0>=C && B>=1 ], cost: 1+B 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Removed unreachable locations (and leaf rules with constant cost): 4.35/2.43 4.35/2.43 Start location: f 4.35/2.43 4.35/2.43 0: f -> g : A'=1, B'=1, [], cost: 1 4.35/2.43 4.35/2.43 6: f -> g : A'=2^C, B'=2^C, C'=0, [ C>=1 ], cost: 1+C 4.35/2.43 4.35/2.43 7: g -> h : B'=0, [ 0>=C && B>=1 ], cost: 1+B 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Eliminated locations (on tree-shaped paths): 4.35/2.43 4.35/2.43 Start location: f 4.35/2.43 4.35/2.43 8: f -> h : A'=1, B'=0, [ 0>=C ], cost: 3 4.35/2.43 4.35/2.43 9: f -> h : A'=2^C, B'=0, C'=0, [ C>=1 && 2^C>=1 ], cost: 2+C+2^C 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Applied pruning (of leafs and parallel rules): 4.35/2.43 4.35/2.43 Start location: f 4.35/2.43 4.35/2.43 9: f -> h : A'=2^C, B'=0, C'=0, [ C>=1 && 2^C>=1 ], cost: 2+C+2^C 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 ### Computing asymptotic complexity ### 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Fully simplified ITS problem 4.35/2.43 4.35/2.43 Start location: f 4.35/2.43 4.35/2.43 9: f -> h : A'=2^C, B'=0, C'=0, [ C>=1 && 2^C>=1 ], cost: 2+C+2^C 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Computing asymptotic complexity for rule 9 4.35/2.43 4.35/2.43 Solved the limit problem by the following transformations: 4.35/2.43 4.35/2.43 Created initial limit problem: 4.35/2.43 4.35/2.43 C (+/+!), 2^C (+/+!), 2+C+2^C (+) [not solved] 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 applying transformation rule (E), replacing 2^C (+/+!) by 1 (+/+!) and C (+) 4.35/2.43 4.35/2.43 resulting limit problem: 4.35/2.43 4.35/2.43 1 (+/+!), C (+), 2+C+2^C (+) [not solved] 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 applying transformation rule (B), deleting 1 (+/+!) 4.35/2.43 4.35/2.43 resulting limit problem: 4.35/2.43 4.35/2.43 C (+), 2+C+2^C (+) [not solved] 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 applying transformation rule (E), replacing 2+C+2^C (+) by 1 (+/+!) and C (+) 4.35/2.43 4.35/2.43 resulting limit problem: 4.35/2.43 4.35/2.43 1 (+/+!), C (+) [not solved] 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 applying transformation rule (B), deleting 1 (+/+!) 4.35/2.43 4.35/2.43 resulting limit problem: 4.35/2.43 4.35/2.43 C (+) [solved] 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Solution: 4.35/2.43 4.35/2.43 C / n 4.35/2.43 4.35/2.43 Resulting cost 2+2^n+n has complexity: Exp 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Found new complexity Exp. 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 Obtained the following overall complexity (w.r.t. the length of the input n): 4.35/2.43 4.35/2.43 Complexity: Exp 4.35/2.43 4.35/2.43 Cpx degree: Exp 4.35/2.43 4.35/2.43 Solved cost: 2+2^n+n 4.35/2.43 4.35/2.43 Rule cost: 2+C+2^C 4.35/2.43 4.35/2.43 Rule guard: [ C>=1 && 2^C>=1 ] 4.35/2.43 4.35/2.43 4.35/2.43 4.35/2.43 WORST_CASE(EXP,?) 4.35/2.43 4.35/2.43 4.35/2.43 ---------------------------------------- 4.35/2.43 4.35/2.43 (4) 4.35/2.43 BOUNDS(EXP, INF) 4.35/2.45 EOF