Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Complexity_C_Integer 2019-03-21 04.38 pair #429989694
details
property
value
status
complete
benchmark
alain.c
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n009.star.cs.uiowa.edu
space
WTC_V2
run statistics
property
value
solver
AProVE
configuration
c_complexity
runtime (wallclock)
2.24369 seconds
cpu usage
3.49164
user time
3.19603
system time
0.295606
max virtual memory
1.8572968E7
max residence set size
217968.0
stage attributes
key
value
starexec-result
WORST_CASE(?, O(n^3))
output
3.37/2.18 WORST_CASE(?, O(n^3)) 3.37/2.20 proof of /export/starexec/sandbox/output/output_files/bench.koat 3.37/2.20 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.37/2.20 3.37/2.20 3.37/2.20 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, n^3). 3.37/2.20 3.37/2.20 (0) CpxIntTrs 3.37/2.20 (1) Koat Proof [FINISHED, 979 ms] 3.37/2.20 (2) BOUNDS(1, n^3) 3.37/2.20 3.37/2.20 3.37/2.20 ---------------------------------------- 3.37/2.20 3.37/2.20 (0) 3.37/2.20 Obligation: 3.37/2.20 Complexity Int TRS consisting of the following rules: 3.37/2.20 eval_alain_start(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb0_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: TRUE 3.37/2.20 eval_alain_bb0_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb8_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_n2 <= 2 * v_y 3.37/2.20 eval_alain_bb0_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb1_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_n2 > 2 * v_y 3.37/2.20 eval_alain_bb1_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb8_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_n2 <= v_z + v_y 3.37/2.20 eval_alain_bb1_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb2_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_n2 > v_z + v_y 3.37/2.20 eval_alain_bb2_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb3_in(v_z, v_n1, v_n2, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_z >= 0 && v_x >= 0 && v_y >= 0 && v_n1 >= 0 && v_n2 >= 0 3.37/2.20 eval_alain_bb2_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb8_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_z < 0 3.37/2.20 eval_alain_bb2_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb8_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_x < 0 3.37/2.20 eval_alain_bb2_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb8_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_y < 0 3.37/2.20 eval_alain_bb2_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb8_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_n1 < 0 3.37/2.20 eval_alain_bb2_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb8_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_n2 < 0 3.37/2.20 eval_alain_bb3_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb4_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_.02 - 1, v_n1, v_n2, v_x, v_y, v_z)) :|: v_.02 - 1 >= 0 3.37/2.20 eval_alain_bb3_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb8_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_.02 - 1 < 0 3.37/2.20 eval_alain_bb4_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb5_in(v_.01, v_.02, v_.03, v_.01, v_.03, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: TRUE 3.37/2.20 eval_alain_bb5_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb6_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_.14 > 0 3.37/2.20 eval_alain_bb5_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb7_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: v_.14 <= 0 3.37/2.20 eval_alain_bb6_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb5_in(v_.01, v_.02, v_.03, v_y, v_.14 - 1, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: TRUE 3.37/2.20 eval_alain_bb7_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_bb3_in(v_.1 + v_y, v_9, v_.1 + v_y, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: TRUE 3.37/2.20 eval_alain_bb8_in(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z) -> Com_1(eval_alain_stop(v_.01, v_.02, v_.03, v_.1, v_.14, v_9, v_n1, v_n2, v_x, v_y, v_z)) :|: TRUE 3.37/2.20 3.37/2.20 The start-symbols are:[eval_alain_start_11] 3.37/2.20 3.37/2.20 3.37/2.20 ---------------------------------------- 3.37/2.20 3.37/2.20 (1) Koat Proof (FINISHED) 3.37/2.20 YES(?, 6*ar_4 + 2*ar_1*ar_4 + 4*ar_0*ar_4 + 2*ar_2*ar_4 + 4*ar_0*ar_4^2 + 15) 3.37/2.20 3.37/2.20 3.37/2.20 3.37/2.20 Initial complexity problem: 3.37/2.20 3.37/2.20 1: T: 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb0in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb0in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ 2*ar_0 >= ar_1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb0in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ ar_1 >= 2*ar_0 + 1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ ar_2 + ar_0 >= ar_1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ ar_1 >= ar_2 + ar_0 + 1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_2, ar_4, ar_1, ar_8, ar_9, ar_10)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= 0 /\ ar_4 >= 0 /\ ar_1 >= 0 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ 0 >= ar_2 + 1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ 0 >= ar_3 + 1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ 0 >= ar_0 + 1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ 0 >= ar_4 + 1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ 0 >= ar_1 + 1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_6 - 1, ar_9, ar_10)) [ ar_6 >= 1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ 0 >= ar_6 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_5, ar_7)) 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ ar_10 >= 1 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ 0 >= ar_10 ] 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_0, ar_10 - 1)) 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_9 + ar_0, ar_8, ar_9 + ar_0, ar_8, ar_9, ar_10)) 3.37/2.20 3.37/2.20 (Comp: ?, Cost: 1) evalalainbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainstop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) 3.37/2.20 3.37/2.20 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10) -> Com_1(evalalainstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10)) [ 0 <= 0 ] 3.37/2.20 3.37/2.20 start location: koat_start 3.37/2.20 3.37/2.20 leaf cost: 0 3.37/2.20 3.37/2.20 3.37/2.20 3.37/2.20 Repeatedly propagating knowledge in problem 1 produces the following problem: 3.37/2.20 3.37/2.20 2: T:
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Complexity_C_Integer 2019-03-21 04.38