Reduction problem to another problem
No, $f$ need not be a NDTM.  To prove a problem is NP-complete by reducing another NP-complete problem to it requires only a Karp reduction, which is a polynomial-time deterministic reduction.  So $f$ would live in the complexity class FP.