2
$\begingroup$

I am reading some notes on parameterized complexity located here. Under the topic of "Kernalization" (section 3, page 4) they state:

When faced with the task of solving an NP-Hard problem, almost every practical computer implementation performs preprocessing steps or data reduction steps. The goal of such a subroutine is to quickly solve the easy parts of a problem instance and reduce it to its difficult core structure that can then be solved by slower exact algorithm. The language of parameterized complexity helps us in formalizing this concept and analyzing the effectiveness of such preprocessing subroutines. This cannot be done in the context of classical complexity since if the bit size of an instance of an NP-Hard problem could be reduced by even just one bit, then this would imply that P=NP.

I am unable to see why this boldface portion is true. Why is it that being able to reduce NP-hard instance of a problem by a single bit implies P = NP?

$\endgroup$

1 Answer 1

7
$\begingroup$

A formal statement of the text you are quoting could be:

For any given NP-complete problem $P \subseteq \Sigma^*$, if P $\neq$ NP, then there is no function $f\colon \Sigma^* \to \Sigma^*$ such that:

  1. $|f(w)| < |w|$ for all but finitely $w \in \Sigma^*$,
  2. $w \in P$ iff $f(w) \in P$, and
  3. $f$ is computable in polynomial time.

Indeed, otherwise, given $w$, it would suffice to iterate $f$ exactly $|w|$ times on it, and then solve (using an NP algorithm) the small instance that you obtain. This algorithm would solve $P$ in polynomial time, and hence would imply that P = NP.

$\endgroup$
1
  • 1
    $\begingroup$ Oh, so it requires $w \in P$ iff $f(w) \in P$. I wasn't thinking about that. I guess it makes sense to do so. Thanks! $\endgroup$
    – Dair
    Commented Dec 27, 2023 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.