/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), ?) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). (0) CpxTRS (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxTRS (3) SlicingProof [LOWER BOUND(ID), 0 ms] (4) CpxTRS (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (6) typed CpxTrs (7) OrderProof [LOWER BOUND(ID), 0 ms] (8) typed CpxTrs (9) RewriteLemmaProof [LOWER BOUND(ID), 1225 ms] (10) BEST (11) proven lower bound (12) LowerBoundPropagationProof [FINISHED, 0 ms] (13) BOUNDS(n^1, INF) (14) typed CpxTrs (15) RewriteLemmaProof [LOWER BOUND(ID), 84 ms] (16) typed CpxTrs (17) RewriteLemmaProof [LOWER BOUND(ID), 392 ms] (18) typed CpxTrs ---------------------------------------- (0) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: if(true, t, e) -> t if(false, t, e) -> e member(x, nil) -> false member(x, cons(y, ys)) -> if(eq(x, y), true, member(x, ys)) eq(nil, nil) -> true eq(O(x), 0(y)) -> eq(x, y) eq(0(x), 1(y)) -> false eq(1(x), 0(y)) -> false eq(1(x), 1(y)) -> eq(x, y) negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) choice(cons(x, xs)) -> x choice(cons(x, xs)) -> choice(xs) guess(nil) -> nil guess(cons(clause, cnf)) -> cons(choice(clause), guess(cnf)) verify(nil) -> true verify(cons(l, ls)) -> if(member(negate(l), ls), false, verify(ls)) sat(cnf) -> satck(cnf, guess(cnf)) satck(cnf, assign) -> if(verify(assign), assign, unsat) S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: if(true, t, e) -> t if(false, t, e) -> e member(x, nil) -> false member(x, cons(y, ys)) -> if(eq(x, y), true, member(x, ys)) eq(nil, nil) -> true eq(O(x), 0(y)) -> eq(x, y) eq(0(x), 1(y)) -> false eq(1(x), 0(y)) -> false eq(1(x), 1(y)) -> eq(x, y) negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) choice(cons(x, xs)) -> x choice(cons(x, xs)) -> choice(xs) guess(nil) -> nil guess(cons(clause, cnf)) -> cons(choice(clause), guess(cnf)) verify(nil) -> true verify(cons(l, ls)) -> if(member(negate(l), ls), false, verify(ls)) sat(cnf) -> satck(cnf, guess(cnf)) satck(cnf, assign) -> if(verify(assign), assign, unsat) S is empty. Rewrite Strategy: FULL ---------------------------------------- (3) SlicingProof (LOWER BOUND(ID)) Sliced the following arguments: satck/0 ---------------------------------------- (4) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: if(true, t, e) -> t if(false, t, e) -> e member(x, nil) -> false member(x, cons(y, ys)) -> if(eq(x, y), true, member(x, ys)) eq(nil, nil) -> true eq(O(x), 0(y)) -> eq(x, y) eq(0(x), 1(y)) -> false eq(1(x), 0(y)) -> false eq(1(x), 1(y)) -> eq(x, y) negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) choice(cons(x, xs)) -> x choice(cons(x, xs)) -> choice(xs) guess(nil) -> nil guess(cons(clause, cnf)) -> cons(choice(clause), guess(cnf)) verify(nil) -> true verify(cons(l, ls)) -> if(member(negate(l), ls), false, verify(ls)) sat(cnf) -> satck(guess(cnf)) satck(assign) -> if(verify(assign), assign, unsat) S is empty. Rewrite Strategy: FULL ---------------------------------------- (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (6) Obligation: TRS: Rules: if(true, t, e) -> t if(false, t, e) -> e member(x, nil) -> false member(x, cons(y, ys)) -> if(eq(x, y), true, member(x, ys)) eq(nil, nil) -> true eq(O(x), 0(y)) -> eq(x, y) eq(0(x), 1(y)) -> false eq(1(x), 0(y)) -> false eq(1(x), 1(y)) -> eq(x, y) negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) choice(cons(x, xs)) -> x choice(cons(x, xs)) -> choice(xs) guess(nil) -> nil guess(cons(clause, cnf)) -> cons(choice(clause), guess(cnf)) verify(nil) -> true verify(cons(l, ls)) -> if(member(negate(l), ls), false, verify(ls)) sat(cnf) -> satck(guess(cnf)) satck(assign) -> if(verify(assign), assign, unsat) Types: if :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat true :: true:false:nil:cons:O:0:1:unsat false :: true:false:nil:cons:O:0:1:unsat member :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat nil :: true:false:nil:cons:O:0:1:unsat cons :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat eq :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat O :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 0 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 1 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat negate :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat choice :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat guess :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat verify :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat sat :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat satck :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat unsat :: true:false:nil:cons:O:0:1:unsat hole_true:false:nil:cons:O:0:1:unsat1_2 :: true:false:nil:cons:O:0:1:unsat gen_true:false:nil:cons:O:0:1:unsat2_2 :: Nat -> true:false:nil:cons:O:0:1:unsat ---------------------------------------- (7) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: member, eq, choice, guess, verify They will be analysed ascendingly in the following order: eq < member member < verify choice < guess ---------------------------------------- (8) Obligation: TRS: Rules: if(true, t, e) -> t if(false, t, e) -> e member(x, nil) -> false member(x, cons(y, ys)) -> if(eq(x, y), true, member(x, ys)) eq(nil, nil) -> true eq(O(x), 0(y)) -> eq(x, y) eq(0(x), 1(y)) -> false eq(1(x), 0(y)) -> false eq(1(x), 1(y)) -> eq(x, y) negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) choice(cons(x, xs)) -> x choice(cons(x, xs)) -> choice(xs) guess(nil) -> nil guess(cons(clause, cnf)) -> cons(choice(clause), guess(cnf)) verify(nil) -> true verify(cons(l, ls)) -> if(member(negate(l), ls), false, verify(ls)) sat(cnf) -> satck(guess(cnf)) satck(assign) -> if(verify(assign), assign, unsat) Types: if :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat true :: true:false:nil:cons:O:0:1:unsat false :: true:false:nil:cons:O:0:1:unsat member :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat nil :: true:false:nil:cons:O:0:1:unsat cons :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat eq :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat O :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 0 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 1 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat negate :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat choice :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat guess :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat verify :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat sat :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat satck :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat unsat :: true:false:nil:cons:O:0:1:unsat hole_true:false:nil:cons:O:0:1:unsat1_2 :: true:false:nil:cons:O:0:1:unsat gen_true:false:nil:cons:O:0:1:unsat2_2 :: Nat -> true:false:nil:cons:O:0:1:unsat Generator Equations: gen_true:false:nil:cons:O:0:1:unsat2_2(0) <=> true gen_true:false:nil:cons:O:0:1:unsat2_2(+(x, 1)) <=> cons(true, gen_true:false:nil:cons:O:0:1:unsat2_2(x)) The following defined symbols remain to be analysed: eq, member, choice, guess, verify They will be analysed ascendingly in the following order: eq < member member < verify choice < guess ---------------------------------------- (9) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: member(gen_true:false:nil:cons:O:0:1:unsat2_2(a), gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n117_2))) -> *3_2, rt in Omega(n117_2) Induction Base: member(gen_true:false:nil:cons:O:0:1:unsat2_2(a), gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, 0))) Induction Step: member(gen_true:false:nil:cons:O:0:1:unsat2_2(a), gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, +(n117_2, 1)))) ->_R^Omega(1) if(eq(gen_true:false:nil:cons:O:0:1:unsat2_2(a), true), true, member(gen_true:false:nil:cons:O:0:1:unsat2_2(a), gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n117_2)))) ->_IH if(eq(gen_true:false:nil:cons:O:0:1:unsat2_2(a), true), true, *3_2) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (10) Complex Obligation (BEST) ---------------------------------------- (11) Obligation: Proved the lower bound n^1 for the following obligation: TRS: Rules: if(true, t, e) -> t if(false, t, e) -> e member(x, nil) -> false member(x, cons(y, ys)) -> if(eq(x, y), true, member(x, ys)) eq(nil, nil) -> true eq(O(x), 0(y)) -> eq(x, y) eq(0(x), 1(y)) -> false eq(1(x), 0(y)) -> false eq(1(x), 1(y)) -> eq(x, y) negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) choice(cons(x, xs)) -> x choice(cons(x, xs)) -> choice(xs) guess(nil) -> nil guess(cons(clause, cnf)) -> cons(choice(clause), guess(cnf)) verify(nil) -> true verify(cons(l, ls)) -> if(member(negate(l), ls), false, verify(ls)) sat(cnf) -> satck(guess(cnf)) satck(assign) -> if(verify(assign), assign, unsat) Types: if :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat true :: true:false:nil:cons:O:0:1:unsat false :: true:false:nil:cons:O:0:1:unsat member :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat nil :: true:false:nil:cons:O:0:1:unsat cons :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat eq :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat O :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 0 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 1 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat negate :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat choice :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat guess :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat verify :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat sat :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat satck :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat unsat :: true:false:nil:cons:O:0:1:unsat hole_true:false:nil:cons:O:0:1:unsat1_2 :: true:false:nil:cons:O:0:1:unsat gen_true:false:nil:cons:O:0:1:unsat2_2 :: Nat -> true:false:nil:cons:O:0:1:unsat Generator Equations: gen_true:false:nil:cons:O:0:1:unsat2_2(0) <=> true gen_true:false:nil:cons:O:0:1:unsat2_2(+(x, 1)) <=> cons(true, gen_true:false:nil:cons:O:0:1:unsat2_2(x)) The following defined symbols remain to be analysed: member, choice, guess, verify They will be analysed ascendingly in the following order: member < verify choice < guess ---------------------------------------- (12) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (13) BOUNDS(n^1, INF) ---------------------------------------- (14) Obligation: TRS: Rules: if(true, t, e) -> t if(false, t, e) -> e member(x, nil) -> false member(x, cons(y, ys)) -> if(eq(x, y), true, member(x, ys)) eq(nil, nil) -> true eq(O(x), 0(y)) -> eq(x, y) eq(0(x), 1(y)) -> false eq(1(x), 0(y)) -> false eq(1(x), 1(y)) -> eq(x, y) negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) choice(cons(x, xs)) -> x choice(cons(x, xs)) -> choice(xs) guess(nil) -> nil guess(cons(clause, cnf)) -> cons(choice(clause), guess(cnf)) verify(nil) -> true verify(cons(l, ls)) -> if(member(negate(l), ls), false, verify(ls)) sat(cnf) -> satck(guess(cnf)) satck(assign) -> if(verify(assign), assign, unsat) Types: if :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat true :: true:false:nil:cons:O:0:1:unsat false :: true:false:nil:cons:O:0:1:unsat member :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat nil :: true:false:nil:cons:O:0:1:unsat cons :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat eq :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat O :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 0 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 1 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat negate :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat choice :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat guess :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat verify :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat sat :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat satck :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat unsat :: true:false:nil:cons:O:0:1:unsat hole_true:false:nil:cons:O:0:1:unsat1_2 :: true:false:nil:cons:O:0:1:unsat gen_true:false:nil:cons:O:0:1:unsat2_2 :: Nat -> true:false:nil:cons:O:0:1:unsat Lemmas: member(gen_true:false:nil:cons:O:0:1:unsat2_2(a), gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n117_2))) -> *3_2, rt in Omega(n117_2) Generator Equations: gen_true:false:nil:cons:O:0:1:unsat2_2(0) <=> true gen_true:false:nil:cons:O:0:1:unsat2_2(+(x, 1)) <=> cons(true, gen_true:false:nil:cons:O:0:1:unsat2_2(x)) The following defined symbols remain to be analysed: choice, guess, verify They will be analysed ascendingly in the following order: choice < guess ---------------------------------------- (15) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: choice(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n125818_2))) -> *3_2, rt in Omega(n125818_2) Induction Base: choice(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, 0))) Induction Step: choice(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, +(n125818_2, 1)))) ->_R^Omega(1) choice(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n125818_2))) ->_IH *3_2 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (16) Obligation: TRS: Rules: if(true, t, e) -> t if(false, t, e) -> e member(x, nil) -> false member(x, cons(y, ys)) -> if(eq(x, y), true, member(x, ys)) eq(nil, nil) -> true eq(O(x), 0(y)) -> eq(x, y) eq(0(x), 1(y)) -> false eq(1(x), 0(y)) -> false eq(1(x), 1(y)) -> eq(x, y) negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) choice(cons(x, xs)) -> x choice(cons(x, xs)) -> choice(xs) guess(nil) -> nil guess(cons(clause, cnf)) -> cons(choice(clause), guess(cnf)) verify(nil) -> true verify(cons(l, ls)) -> if(member(negate(l), ls), false, verify(ls)) sat(cnf) -> satck(guess(cnf)) satck(assign) -> if(verify(assign), assign, unsat) Types: if :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat true :: true:false:nil:cons:O:0:1:unsat false :: true:false:nil:cons:O:0:1:unsat member :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat nil :: true:false:nil:cons:O:0:1:unsat cons :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat eq :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat O :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 0 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 1 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat negate :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat choice :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat guess :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat verify :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat sat :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat satck :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat unsat :: true:false:nil:cons:O:0:1:unsat hole_true:false:nil:cons:O:0:1:unsat1_2 :: true:false:nil:cons:O:0:1:unsat gen_true:false:nil:cons:O:0:1:unsat2_2 :: Nat -> true:false:nil:cons:O:0:1:unsat Lemmas: member(gen_true:false:nil:cons:O:0:1:unsat2_2(a), gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n117_2))) -> *3_2, rt in Omega(n117_2) choice(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n125818_2))) -> *3_2, rt in Omega(n125818_2) Generator Equations: gen_true:false:nil:cons:O:0:1:unsat2_2(0) <=> true gen_true:false:nil:cons:O:0:1:unsat2_2(+(x, 1)) <=> cons(true, gen_true:false:nil:cons:O:0:1:unsat2_2(x)) The following defined symbols remain to be analysed: guess, verify ---------------------------------------- (17) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: guess(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n126289_2))) -> *3_2, rt in Omega(n126289_2) Induction Base: guess(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, 0))) Induction Step: guess(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, +(n126289_2, 1)))) ->_R^Omega(1) cons(choice(true), guess(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n126289_2)))) ->_IH cons(choice(true), *3_2) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (18) Obligation: TRS: Rules: if(true, t, e) -> t if(false, t, e) -> e member(x, nil) -> false member(x, cons(y, ys)) -> if(eq(x, y), true, member(x, ys)) eq(nil, nil) -> true eq(O(x), 0(y)) -> eq(x, y) eq(0(x), 1(y)) -> false eq(1(x), 0(y)) -> false eq(1(x), 1(y)) -> eq(x, y) negate(0(x)) -> 1(x) negate(1(x)) -> 0(x) choice(cons(x, xs)) -> x choice(cons(x, xs)) -> choice(xs) guess(nil) -> nil guess(cons(clause, cnf)) -> cons(choice(clause), guess(cnf)) verify(nil) -> true verify(cons(l, ls)) -> if(member(negate(l), ls), false, verify(ls)) sat(cnf) -> satck(guess(cnf)) satck(assign) -> if(verify(assign), assign, unsat) Types: if :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat true :: true:false:nil:cons:O:0:1:unsat false :: true:false:nil:cons:O:0:1:unsat member :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat nil :: true:false:nil:cons:O:0:1:unsat cons :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat eq :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat O :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 0 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat 1 :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat negate :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat choice :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat guess :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat verify :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat sat :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat satck :: true:false:nil:cons:O:0:1:unsat -> true:false:nil:cons:O:0:1:unsat unsat :: true:false:nil:cons:O:0:1:unsat hole_true:false:nil:cons:O:0:1:unsat1_2 :: true:false:nil:cons:O:0:1:unsat gen_true:false:nil:cons:O:0:1:unsat2_2 :: Nat -> true:false:nil:cons:O:0:1:unsat Lemmas: member(gen_true:false:nil:cons:O:0:1:unsat2_2(a), gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n117_2))) -> *3_2, rt in Omega(n117_2) choice(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n125818_2))) -> *3_2, rt in Omega(n125818_2) guess(gen_true:false:nil:cons:O:0:1:unsat2_2(+(1, n126289_2))) -> *3_2, rt in Omega(n126289_2) Generator Equations: gen_true:false:nil:cons:O:0:1:unsat2_2(0) <=> true gen_true:false:nil:cons:O:0:1:unsat2_2(+(x, 1)) <=> cons(true, gen_true:false:nil:cons:O:0:1:unsat2_2(x)) The following defined symbols remain to be analysed: verify