# Reduction from NP-complete problem to unknown complexity problem and vice-versa

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?

• In your second statement, how can you say A is "at least" when $A \le B$ ? – Optidad Jun 3 '19 at 9:31
• 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. – Marcus Ritt Jun 3 '19 at 10:10
• 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$. – Vor Jun 3 '19 at 12:12

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