1
$\begingroup$

Conceptually, I know that reducing a problem $Y$ that's NP-complete to a problem $X$ implies that $X$ is at least as hard as $Y$, implying $X$ is also NP-complete. So if any NPC problem, say $Z$, can be solved in polynomial time, then that implies $P = NP$, since any other NP-complete problem can be reduced to $Z$ in polynomial time, and then solved in polynomial time. But what does it mean to reduce a problem in $P$ to a problem in $NP$? I feel like this is self-evident (problems in P are no harder than problems in $NP$), but is there any example that can make this clearer?

$\endgroup$
  • $\begingroup$ When taking boolean formulas, we can say that HornSAT already is a subcase of SAT and thus a member of NP. And in fact every NPC problem under some restrictions becomes P problem. $\endgroup$ – rus9384 Nov 13 '17 at 12:19
  • $\begingroup$ " implying X is also NP-complete" -- only if X is in NP. $\endgroup$ – Raphael Nov 13 '17 at 12:28
  • $\begingroup$ " I feel like this is self-evident" -- pretty much, yes. Follow the definitions. $\endgroup$ – Raphael Nov 13 '17 at 12:28
4
$\begingroup$

Note: this answer assumes that we are considering polynomial-time reductions (and not e.g. log-space ones).


If $A$ belongs to $P$, then we can reduce $A$ to any nontrivial language, i.e. any $B\neq \emptyset,\Sigma^*$.

Reducing $A$ to $B$ can be done as follows. Fix $b_1\in B, b_0 \in \overline B$ arbitrarily. The reduction algorithm then takes an input $x$ and tests whether $x\in A$: if that holds, return $b_1$, otherwise return $b_0$.

Note that all of this can be run in polynomial time since $A$ belongs to $P$. This allows to solve the $A$ instance in the reduction algorithm itself, trivializing the reduction.

This proves that problems in $P$ are indeed the easiest possible ones, according to the "polynomial-time reduction" preorder.

$\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.