# Clarifications on polynomial reducibility for problems in P and NP-complete

Can I always increase the complexity of a problem via polynomial reduction? (in which case 'reduction' is really a misnomer) For example, if I have a classic P problem (say, finding the smallest element in an array, by iterating through and making comparisons with the smallest value found thus far), what would be a corresponding problem in NP-complete (obtained via polynomial reduction)? Or, would it be possible to polynomially reduce a constant time (worst case) algorithm into a polynomial time algorithm (basically performing unnecessary executions for all n of the input for nothing)?

As a side request, I'm looking for a basic reference that deals with how one problem (in P or NP-complete) can be reduced (in polynomial time) to a problem in (P or NP-complete). Most of the things I found online are beyond scope or vague. I'm looking for an easy way to figure out whether a certain Problem A (in P or NP-complete) can be polynomially reduced to a Problem B (in P or NP-complete).

• the aim of a polynomial-time reduction is not to increase the complexity of a problem, but instead to show that an algorithm that solves a problem B can be efficiently used to solve another problem A (and we say that A is polynomial-time reducible to B).
– Vor
Oct 8 '12 at 21:52