0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ There must be a non-deterministic poly-time reduction. However, I don't know about reductions that use non-determinism. $\endgroup$ – rus9384 Aug 7 '17 at 17:42
  • $\begingroup$ @rus9384 I think you are wrong $\endgroup$ – miracle173 Aug 7 '17 at 17:55
  • 1
    $\begingroup$ @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$. $\endgroup$ – miracle173 Aug 7 '17 at 17:57
  • $\begingroup$ @miracle173, why am I wrong? Every poly-time deterministic reduction is also poly-time non-deterministic reduction. Reversal is true iff $\mathsf{P = NP}$. $\endgroup$ – rus9384 Aug 7 '17 at 18:21
  • 1
    $\begingroup$ Hint: look at the definition of NP-completeness. It's all there. $\endgroup$ – Raphael Aug 7 '17 at 21:31
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.