5
$\begingroup$

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$

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

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.

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