Yes, NAND gates can implement root finding algorithms for arbitrary polynomials. For example a variant of Newton’s method can be used (there are also better algorithms for circuits specifically).

This can be done in polynomial time as well.

This is fairly obvious if you think about that your computer can do the same thing and it’s just a fancy circuit.