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?
$\begingroup$
$\endgroup$
9
-
$\begingroup$ There must be a non-deterministic poly-time reduction. However, I don't know about reductions that use non-determinism. $\endgroup$– rus9384Commented Aug 7, 2017 at 17:42
-
$\begingroup$ @rus9384 I think you are wrong $\endgroup$– miracle173Commented Aug 7, 2017 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$– miracle173Commented Aug 7, 2017 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$– rus9384Commented Aug 7, 2017 at 18:21
-
1$\begingroup$ Hint: look at the definition of NP-completeness. It's all there. $\endgroup$– RaphaelCommented Aug 7, 2017 at 21:31
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
answered Aug 7, 2017 at 18:39