# Reduction problem to another problem

I would like to show that a problem $A$ is $NP\text{-complete}$. So, I am trying to reduce 3-SAT problem to $A$. Reduction is kind of function, let say $f$. What is necessary complexity of $f$? Probably, it has be in $NP$. But, does it mean that $f$ must be a non-deterministic Turing machine working in polynomial time?

• There must be a non-deterministic poly-time reduction. However, I don't know about reductions that use non-determinism. – rus9384 Aug 7 '17 at 17:42
• @rus9384 I think you are wrong – miracle173 Aug 7 '17 at 17:55
• @Carol; 1) search for reduction and complete on this site. 2) $P$ isnt a good name for a problem in this context because $P$ is also used for the complexity class $P$. – miracle173 Aug 7 '17 at 17:57
• @miracle173, why am I wrong? Every poly-time deterministic reduction is also poly-time non-deterministic reduction. Reversal is true iff $\mathsf{P = NP}$. – rus9384 Aug 7 '17 at 18:21
• Hint: look at the definition of NP-completeness. It's all there. – Raphael Aug 7 '17 at 21:31

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.