On the computational complexity of conservative computing