We are left with following problem, upon which TcT provides the
certificate YES(?,O(1)).

Strict Trs:
  { primes() -> sieve(from(s(s(0()))))
  , sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y))))
  , from(X) -> cons(X, n__from(s(X)))
  , from(X) -> n__from(X)
  , cons(X1, X2) -> n__cons(X1, X2)
  , head(cons(X, Y)) -> X
  , tail(cons(X, Y)) -> activate(Y)
  , activate(X) -> X
  , activate(n__from(X)) -> from(X)
  , activate(n__filter(X1, X2)) -> filter(X1, X2)
  , activate(n__cons(X1, X2)) -> cons(X1, X2)
  , if(true(), X, Y) -> activate(X)
  , if(false(), X, Y) -> activate(Y)
  , filter(X1, X2) -> n__filter(X1, X2)
  , filter(s(s(X)), cons(Y, Z)) ->
    if(divides(s(s(X)), Y),
       n__filter(s(s(X)), activate(Z)),
       n__cons(Y, n__filter(X, sieve(Y)))) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(1))

Arguments of following rules are not normal-forms:

{ sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y))))
, head(cons(X, Y)) -> X
, tail(cons(X, Y)) -> activate(Y)
, filter(s(s(X)), cons(Y, Z)) ->
  if(divides(s(s(X)), Y),
     n__filter(s(s(X)), activate(Z)),
     n__cons(Y, n__filter(X, sieve(Y)))) }

All above mentioned rules can be savely removed.

We are left with following problem, upon which TcT provides the
certificate YES(?,O(1)).

Strict Trs:
  { primes() -> sieve(from(s(s(0()))))
  , from(X) -> cons(X, n__from(s(X)))
  , from(X) -> n__from(X)
  , cons(X1, X2) -> n__cons(X1, X2)
  , activate(X) -> X
  , activate(n__from(X)) -> from(X)
  , activate(n__filter(X1, X2)) -> filter(X1, X2)
  , activate(n__cons(X1, X2)) -> cons(X1, X2)
  , if(true(), X, Y) -> activate(X)
  , if(false(), X, Y) -> activate(Y)
  , filter(X1, X2) -> n__filter(X1, X2) }
Obligation:
  innermost runtime complexity
Answer:
  YES(?,O(1))

The input was oriented with the instance of 'Small Polynomial Path
Order (PS,0-bounded)' as induced by the safe mapping

 safe(primes) = {}, safe(sieve) = {}, safe(from) = {1},
 safe(s) = {1}, safe(0) = {}, safe(cons) = {1, 2},
 safe(n__from) = {1}, safe(activate) = {1}, safe(if) = {2},
 safe(true) = {}, safe(false) = {}, safe(filter) = {1, 2},
 safe(n__filter) = {1, 2}, safe(n__cons) = {1, 2}

and precedence

 primes > from, from > cons, activate > from, activate > cons,
 activate > filter, if > activate .

Following symbols are considered recursive:

 {}

The recursion depth is 0.

For your convenience, here are the satisfied ordering constraints:

                          primes() > sieve(from(; s(; s(; 0())));)
                                                                  
                         from(; X) > cons(; X,  n__from(; s(; X)))
                                                                  
                         from(; X) > n__from(; X)                 
                                                                  
                   cons(; X1,  X2) > n__cons(; X1,  X2)           
                                                                  
                     activate(; X) > X                            
                                                                  
          activate(; n__from(; X)) > from(; X)                    
                                                                  
  activate(; n__filter(; X1,  X2)) > filter(; X1,  X2)            
                                                                  
    activate(; n__cons(; X1,  X2)) > cons(; X1,  X2)              
                                                                  
                 if(true(),  Y; X) > activate(; X)                
                                                                  
                if(false(),  Y; X) > activate(; Y)                
                                                                  
                 filter(; X1,  X2) > n__filter(; X1,  X2)         
                                                                  

Hurray, we answered YES(?,O(1))