0
$\begingroup$

A problem $\Pi'$ is pseudo-polynomially reducible to the problem $\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially bounded time, such that, given the solution $S_I$ to $I$, the solution $S_I'$ to $I'$ can be found in pseudo-polynomial time.

It follows that, $\forall \Pi,\Pi' \in NP$, if $\Pi'$ is strongly NP-complete, and $\Pi' \leq_{pp} \Pi$, then $\Pi$ is strongly NP-complete.

And it is easy to show that "3-Partition $\leq_{pp}$ Partition."

Hence, I can conclude that Partition is strongly NP-complete. (However, we already know that Partition problem is ordinary NP-complete.)

Am I missing something!?

Improve this question
$\endgroup$
2
  • $\begingroup$ @TomvanderZanden: This comment is from another user here cs.stackexchange.com/questions/39753/…: Every known reduction from 3-Partition to 2-Partition creates numbers that are exponentially bigger than the original numbers. $\endgroup$
    – Mohammad Namakshenas
    Jun 13, 2019 at 15:20
  • $\begingroup$ Why do you think it is easy to reduce 3-partition to partition in pptime $\endgroup$
    – Narek Bojikian
    Nov 11, 2019 at 10:21

1 Answer 1

Reset to default
1
$\begingroup$

The claim

It follows that, $\forall \Pi,\Pi' \in NP$, if $\Pi'$ is strongly NP-complete, and $\Pi' \leq_{pp} \Pi$, then $\Pi$ is strongly NP-complete.

is wrong (at least for how "pseudo-polynomically reducible" is defined here).

If $\Pi'$ is strongly $NP$-complete, then ``pseudo-polynomially reducible'' is equivalent to polynomially reducible.

Recall that a problem is strongly $NP$-complete if it is $NP$-complete even if we assume all the integers that appear in the input are polynomial in the length of the input.

Recall that an algorithm runs in pseudopolynomial time if it runs in polynomial time in the integers that appear in the input.

So, a pseudopolynomial reduction must run in time polynomial in the integers that appear in the input. Which, for a strongly $NP$-complete problem, can be assumed to be polynomial in the length of the input. Which means the reduction must run in time polynomial in the length of input.

So, if $\Pi'$ is strongly $NP$-complete, $\Pi' \leq_{pp} \Pi$ is equivalent to $\Pi' \leq_p \Pi$. Clearly, the existence of such a reduction does not imply that $\Pi$ is strongly $NP$-hard.

The only place in the literature that I can find any mention of this notion of ``pseudopolynomial reduction'' is in the appendix an OR & Management Science book. I cannot find any other literature mentioning this notion; one would expect to be able to find some mention of it in complexity theory circles.

We should use a different definition for $\leq_{pp}$. A pseudopolynomial reduction should be defined as a reduction, running in pseudpolynomial time, that in addition does not increase integer values in the input more than polynomially. Then the claim would hold true.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The claim "$\forall \Pi,\Pi' \in NP$, if $\Pi'$ is strongly NP-complete, and $\Pi' \leq_{pp} \Pi$, then $\Pi$ is strongly NP-complete." is from books.google.com/… . $\endgroup$
    – Mohammad Namakshenas
    Jun 13, 2019 at 15:54
  • $\begingroup$ That book is wrong. $\endgroup$
    – Tom van der Zanden
    Jun 13, 2019 at 17:01
  • $\begingroup$ Thanks for your answer. Actually, I want to show that the reduction "3-Partition $\leq_p$ Partition" can't give an instance of the polynomially-bounded size of the input. $\endgroup$
    – Mohammad Namakshenas
    Jun 13, 2019 at 17:51
  • $\begingroup$ I'm not sure what you mean by "an instance of the polynomially-bounded size of the input". But I think you cannot prove what you want to prove without assuming $P\not = NP$. $\endgroup$
    – Tom van der Zanden
    Jun 13, 2019 at 18:18
  • $\begingroup$ @TomvanderZanden He basically means, that he determines the time complexity relating to the input length not magintude. For example the subset-sum problem has as input $n$ integers and integer $k$ (the target sum). If I would write $T(k,n)=k*n \in O(k*n)$ this would be wrong, because $k$ depends on the actual number and not at the number of bits that are needed to encode $k$. Assume we add x bit to $k$, we would double $k$ $x$ times (cyclic left bitshift). Thus $T(n;k+x)= 2^x*k*n$ Here we would write $T(n) \in O^{~}(k*n)$ to denote that we hide a logarithmic factor in $k$. $\endgroup$
    – Panzerkroete
    Jun 14, 2019 at 2:02

Your Answer

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

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