# Prove that NP is closed under karp reduction?

A complexity class $$\mathbb{C}$$ is said to be closed under a reduction if:

$$A$$ reduces to $$B$$ and $$B \in \mathbb{C}$$ $$\implies$$ $$A \in \mathbb{C}$$

How would you go about proving this if $$\mathbb{C} = NP$$ and the reduction to be the karp reduction? i.e.

Prove that if $$A$$ karp reduces to $$B$$ and $$B \in NP$$ $$\implies$$ $$A \in NP$$

• Try using the definitions. – Yuval Filmus Apr 6 '19 at 19:09
• @YuvalFilmus thanks for the advice, this helped me figure it out! – Ankit Bahl Apr 6 '19 at 20:06

I was able to figure it out. In case anyone (mans in ECE 406) was wondering:

$$B \in NP$$ means that there exists a non-deterministic polynomial time algorithm for $$B$$. Let's call that $$b(i)$$, where $$i$$ is the input to $$B$$.

$$A$$ karp reducing to $$B \implies$$ that there exists a function $$m$$ such that $$m$$ can take an input $$i$$ to $$A$$ and map it to some input $$m(i)$$ for $$B$$, and if an instance of $$i$$ is true for $$A$$ then $$m(i)$$ is true for B (and same for false case),

Therefore, an algorithm for $$A$$ can be made as follows:

$$A (i)$$

1. Take input $$i$$ and apply $$m$$ to yield $$m(i)$$
2. Apply $$b$$ with input $$m(i)$$

This yields an output for $$A$$. Since both $$m$$ and $$b$$ are non-deterministic polynomial time, this algorithm is non-deterministic polynomial time. Therefore $$A$$ must be in NP.