<p>In my opinion, this is an utter triviality, so unimportant that no one would remark on it.   Furthermore, the chance that <span class="math-container">$t$</span> numbers chosen at random would have gcd > 1 is vanishingly small once <span class="math-container">$t$</span> is large.  (There is an explicit formula, which says that t integers chosen at random from the interval [1..n] will have gcd 1 with probability tending to <span class="math-container">$1/\zeta(t)$</span> as <span class="math-container">$n$</span> gets large.)</p>

CC BY-SA 4.0
2018-12-10T13:26:55.220Z
2018-12-10T13:26:55.220Z
Jeffrey Shallit
<p>I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" instances are easier to solve than the really hard ones.. (and maybe this applies to other problems as well)</p>

<p>I was wondering if this has been described (and analyzed) elsewhere, any reference will be greatly appreciated.</p>

<hr>

<p>The values in the input instance must have <span class="math-container">$GCD = 1$</span>, if greater, the instance (let's name it <span class="math-container">$A$</span>) will look harder than it really is, due an artificial input length
The real hardness, will only be known once all input values, and the target, have been divided by their GCD, creating a B instance from A, with <span class="math-container">$|B| &lt; |A| $</span>. 
The reason is, when this input instances are presented to the algorithm, both instances will take the same number of steps to compute while having a supposedly different hardness (density). This characteristic can be used to present a <span class="math-container">$n\ge p$</span> instance, when in reality is <span class="math-container">$n&lt;p$</span>, just the values, and the target, have been multiplied by an integer long enough to produce the desired artificial length.</p>

<p>This was found when experimenting with edge cases, trying to better understand the input length impact in the algorithm, if a instance <span class="math-container">$n=100$</span> / <span class="math-container">$p=16$</span> takes <span class="math-container">$x$</span> total steps, and we create an artificial instance by multiplying the values and the target by the same integer, causing all the values including the target to have <span class="math-container">$\approx 100$</span> bits, the resultant instance, having <span class="math-container">$\approx 10000$</span> bits will take exactly the same number of steps like the original one having <span class="math-container">$\approx 1600$</span> bits, that is, <span class="math-container">$x$</span> steps.</p>

<co.combinatorics><np-hardness><np-complete><subset-sum>
Subset Sum Problem and hard looking instances that are not really hard
Jesus Salas
# Subset Sum Problem and hard looking instances that are not really hard

(Asked by: username_0 on 2018-12-09)

I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" instances are easier to solve than the really hard ones.. (and maybe this applies to other problems as well)

I was wondering if this has been described (and analyzed) elsewhere, any reference will be greatly appreciated.

---

The values in the input instance must have $GCD = 1$, if greater, the instance (let's name it $A$) will look harder than it really is, due an artificial input length
The real hardness, will only be known once all input values, and the target, have been divided by their GCD, creating a B instance from A, with $|B| < |A| $.
The reason is, when this input instances are presented to the algorithm, both instances will take the same number of steps to compute while having a supposedly different hardness (density). This characteristic can be used to present a $n\ge p$ instance, when in reality is $n, just the values, and the target, have been multiplied by an integer long enough to produce the desired artificial length.

This was found when experimenting with edge cases, trying to better understand the input length impact in the algorithm, if a instance $n=100$ / $p=16$ takes $x$ total steps, and we create an artificial instance by multiplying the values and the target by the same integer, causing all the values including the target to have $\approx 100$ bits, the resultant instance, having $\approx 10000$ bits will take exactly the same number of steps like the original one having $\approx 1600$ bits, that is, $x$ steps.

**Tags:** co.combinatorics, np-hardness, np-complete, subset-sum


---

## 1 answers

### Answer by username_1 on 2018-12-10. Score: 5 | Accepted answer

In my opinion, this is an utter triviality, so unimportant that no one would remark on it. Furthermore, the chance that $t$ numbers chosen at random would have gcd > 1 is vanishingly small once $t$ is large. (There is an explicit formula, which says that t integers chosen at random from the interval [1..n] will have gcd 1 with probability tending to $1/\zeta(t)$ as $n$ gets large.)


---

