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<p$, 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.
