1
$\begingroup$

Suppose I have two problems: $B$, which is NP-complete, and $A$, of unknown complexity.

Question:

  • If I show that $B \le A$ I can state that $A$ is also NP-complete because the two required conditions are satisfied: (i) $A$ is in NP; (ii) I reduced a NP-complete problem to $A$.
  • If I show that $A \le B$ I can say that $B$ is at least hard as $A$, so $A$ is at least NP-complete, but can be harder.

Are these statements correct?

$\endgroup$
  • $\begingroup$ In your second statement, how can you say A is "at least" when $A \le B$ ? $\endgroup$ – Optidad Jun 3 '19 at 9:31
  • $\begingroup$ The second statement is false: reducing A to B does not imply A’s NP-completeness. A could be in P, for example. In the first: how do you conclude that A is NP? If A is of unknown complexity it could be EXP-complete, for example. $\endgroup$ – Marcus Ritt Jun 3 '19 at 10:10
  • $\begingroup$ Also the first statement is incorret: if $B \leq A$ then $A$ (of "unknown complexity") is NP-hard; in order to prove that it is NP-complete you must also prove that it is contained in $NP$. $\endgroup$ – Vor Jun 3 '19 at 12:12
2
$\begingroup$

I shall assume "$\le$" indicates a poly-time, many-one (i.e., Karp) reduction. This seems to be the case since you are referring to NP-completeness.

If I show that $B \le A$ I can state that A is also NP-complete because the two required conditions are satisfied: (i) A is in NP (ii) i reduced a NP -complete problem to A.

If $B \le A$, that is, $B$ is reducible to $A$, then $A$ is necessarily $\mathbf{NP}$-hard, that is, any problem in $C \in \mathbf{NP}$ is reducible to $A$ (i.e., $C \le A$). This is because any problem $C \in \mathbf{NP}$ is reducible to $B$ (due to the $\mathbf{NP}$-completeness of $B$) and we have $C \le B \le A$; using the transitivity of (this form of) reduction we obtain $C \le A$. However, this does not at all imply that $A \in \mathbf{NP}$—otherwise, any $\mathbf{NP}$-hard problem would be $\mathbf{NP}$-complete! To prove $A$ is $\mathbf{NP}$-complete, thus, you would also have to prove $A \in \mathbf{NP}$ separately.

If I show that $A \le B$ I can say that $B$ is at least hard as $A$, so $A$ is at least NP-complete, but can be harder.

$A \le B$ means $A$ is reducible to $B$, which can be reformulated as $B$ being at least as hard as $A$, as you have stated. In no way does this imply that $A$ is $\mathbf{NP}$-complete. Granted, it could be the case, but, for all we know, $A$ could be in $\mathbf{P}$, a regular language, or even trivial (i.e., $\Sigma^\ast$ or $\varnothing$).

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