To my understanding, as long as we can find some polytime function $f$ such that $\forall x:x \in A \Longleftrightarrow f(x) \in B, x\notin A \Longleftrightarrow f(x) \notin B$, it follows that if $A$ is NP-complete and B is in NP, then B is also in NP-complete.

My question is about what sort of 'things' we can do to obtain reductions from NP-completeness. That is, I want to know if $f$ is allowed to do anything so long as it is still done in polytime and satisfies the above property? If not, then what sort of limitations are there?


Your understanding is correct.

The only restriction is the one you mention: the reduction must work in polynomial time. That is, there must be some algorithm and some polynomial function $t(n)$ (e.g. $t(n)=n^5+n^3+42$) such that, on all inputs $x$ of length $n$, the algorithm outputs $f(x)$ and the time it takes the algorithm to do that is less than or equal to $t(n)$.

To answer concretely what "things" you may do, I can't! Anything you can think of that takes polynomial time: perfect matching, integer multiplication, some variants of linear programming... graph isomorphism? Counting the number of solutions to the traveling salesman problem? If you can do it in polynomial time, then yes!

To read some posts on this site about NP Completeness, click here to search for posts about that topic.

| cite | improve this answer | |

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.