You prove that vertex cover reduces to some problem A, does that mean that A is NP-Complete?

My question is essentially the title. Let's say you have some random problem A. You prove that Vertex Cover (which is NP-Complete) reduces to A. You know nothing else about A besides that Vertex Cover reduces to it. Does that mean that A is NP-Complete? Or because we don't know if P = NP, we technically don't know if A is in NP or P?

Let's start with the relevant definitions:


A problem $A$ is NP-complete if:

• $A$ is in NP, and

• $A$ is NP-hard.

A problem $A$ is NP-hard if for every problem $B$ in NP, there is a polytime reduction from $B$ to $A$.

Using these definitions, you can prove the following result:


If a problem $B$ is NP-hard and there is a reduction from $B$ to $A$, then problem $A$ is also NP-hard.

Applying this to your problem, if there is a reduction from vertex cover to $A$, then $A$ is NP-hard. If $A$ is also in NP, then it is furthermore NP-complete. Whether P=NP or not has absolutely no bearing on this.

Note that there are NP-hard problems which are provably not in NP. For example, the halting problem is NP-hard, but is known not to be in NP.

StackExchange Computer Science Q#118643, answer score: 4