YES(?,POLY)

'Pop* with parameter subtitution (timeout of 60.0 seconds)'
-----------------------------------------------------------
Answer:           YES(?,POLY)
Input Problem:    innermost runtime-complexity with respect to
  Rules:
    {  filter(cons(X), 0(), M) -> cons(0())
     , filter(cons(X), s(N), M) -> cons(X)
     , sieve(cons(0())) -> cons(0())
     , sieve(cons(s(N))) -> cons(s(N))
     , nats(N) -> cons(N)
     , zprimes() -> sieve(nats(s(s(0()))))}

Proof Output:    
  The input was oriented with the instance of POP* as induced by the precedence
  
   filter > sieve, filter > nats, zprimes > sieve, zprimes > nats,
   filter ~ zprimes, sieve ~ nats
  
  and safe mapping
  
   safe(filter) = {1, 2, 3}, safe(cons) = {1}, safe(0) = {},
   safe(s) = {1}, safe(sieve) = {1}, safe(nats) = {},
   safe(zprimes) = {} .
  
  For your convenience, here is the input in predicative notation:
  
   Rules:
    {  filter(; cons(; X), 0(), M) -> cons(; 0())
     , filter(; cons(; X), s(; N), M) -> cons(; X)
     , sieve(; cons(; 0())) -> cons(; 0())
     , sieve(; cons(; s(; N))) -> cons(; s(; N))
     , nats(N;) -> cons(; N)
     , zprimes() -> sieve(; nats(s(; s(; 0()));))}