NP Complete, Asymmetric Split

Asymmetric Split

Given a collection of positive integers, and another positive integer b that is less than the total t, is there a subcollection of integers that sums to b? Of course the remaining integers will sum to t-b.

Reduce this to exact cover. Each of the sets in the problem instance will become a number, and numbers combine to produce b iff the corresponding sets produce an exact cover for U.

Let e be an element of U and suppose e appears in j different sets. Let k be log₂(j), rounded up. Each number reserves k bits for the element e. If the set doesn't contain e, these bits are set to 0. If the set contains e, place a 1 in the least significant bit. If all the numbers are added together, these k bits are filled with the number j. Still, there is no carry operation into the next field. You can see how many sets use e simply by looking at these k bits.

Do this for all e in U, and let b be the number that has a 1 in each field. A sum is equal to b iff each element e is used exactly once, iff the corresponding sets form an exact cover for U.

Notice that the integers in this problem are distinct, as each comes from a different set. Also, the number of sets that create the partition is prescribed, hence the number of integers that will sum to b is prescribed. You know in advance how many integers to select, but that doesn't help.

Symmetric Split

The problem remains np complete even if b is half of t. Given b and t as above, let u = 3t+b and let v = 4t-b. The total is now 8t. A symmetric split sums to 4t. This includes u or v, but not both. We are left with b or t-b, which solves the original problem.

Product is -1 mod p

Given an instance of symmetric split, where t = 2b, find a prime p that is 1 mod t. I'll assume this can be done, and p isn't hugely bigger than t. I think this relies on the Riemann hypothesis, or something weird like that. Find z a primitive element mod p. Again, this can be done quickly if rh is true. Let y = z raised to the (p-1)/t. If w_i is an integer in the splitting problem, let y_i = y raised to the w_i. There is a subset of these integers y_i whose product is -1 mod p, iff the corresponding set of integers w_i sums to b. Therefore, finding a product equal to -1 mod p is, with a few disclaimers, np complete.

Choose p = 1 mod b, and look for a proper collection of y_i, some of them and not all of them, having a product of 1. This is np complete.

mod n

Find a distinct prime p for each e in U, such that p is larger than j, where j is the number of times e appears in U. Let n be the product over all these primes. Let y_i be the unique number mod n that is 1 mod p when the corresponding set contains e, and 0 mod p otherwise. Let b be 1 mod p for every prime. Instead of looking at fields within the decimal or binary representation of the integer, we are looking mod p; but the idea is the same. A subcollection of integers sums to b mod n iff U is partitioned, iff the underlying boolean expression is satisfied.

The multiplicative version is similar. When the i^th set contains e, let y_i = q mod p, where q is primitive. Otherwise y_i = 1 mod p. Let b be primitive for every p. Now the product of a subcollection of integers equals b mod n iff U is partitioned, iff the underlying boolean expression is satisfied.

Of course this is a round about way to get to mod n. An easier way is to choose any n larger than t. In fact n can be prime if you like. Now addition mod n is simply addition, and we are looking for a subcollection that sums to b (mod n). Similarly, n can be any prime larger than t+1. Let z be primitive, and let each y_i be z raised to the w_i. Multiplication adds the exponents, and we are looking for a subcollection whose product is z^b.

Product Split

What if we want to multiply integers together to get an integer b, with no modulus? The additive version can be converted into a multiplicative version by mapping each w_i to 2^w_i. Take logs to go back. However, additive integers could be thousands of digits long. Raise 2 to this power, and the transformation is exponential. We are no longer in the polynomial realm.

There is a better transformation that does the trick. Assign a unique prime to each e in U. Start with 2, and proceed through 3, 5, 7, 11, etc. The prime number theorem tells us there are plenty of small primes to choose from. We don't have to jump from 59 to 990013, and then into the trillions. Multiply primes together to get an integer corresponding to each subset of U. Multiply all the primes together to get b. The transformation is polynomial, and the fundamental theorem of arithmetic allows us to map back to the original instance of exact cover. Therefore, writing b as a product of a subset of a given set of integers is np complete.

Product in Range

Let's put some slop in the original, additive version of this problem. Let n be the number of integers in the collection. For each integer w_i, add any ε strictly between 0 and 1/n. The sum of any subcollection now falls in the range (b,b+1) iff the original subcollection sums to b. Asking whether there are rational numbers, each in a certain range, whose sum lies in a given range, is np complete.

To give us more wiggle room, choose ε between 1/n² and 1/n-1/n². Now the sum lies between b+1/n and b+1-1/n.

Divide each w_i, and b, by a large power of 2, or a large power of 10; whatever is convenient for your representation. This is like a change of units, and does not affect the subcollections that sum to something in a given range. The transformation basically puts a decimal point and some zeros in front of each number.

Take the exponential of each number. Remember that when r is small, E^r is approximately 1+r, and we can make this approximation as tight as we like, simply by bringing in a few more zeros at the front. Similarly, log(1+r) is approximately r. Multiply exp(w_i) and exp(w_j) and extract the first block of decimal digits, and you are really adding w_i and w_j. The noise in these transformations are small numbers that fit within our slop. Start with a collection of real numbers, each within its prescribed range, and ask whether there is a subcollection whose product lies in a certain range. This is np complete.

Recall that the size of the subcollection is predetermined. Multiply each w_i by a large number j, and multiply b by an appropriate power of j. The product in range problem remains the same, but now each w_i can be chosen from a large span of integers. With a little help from analytic number theory, there are plenty of primes to choose from. So we have a new np complete problem: given a collection of distinct primes, and a range of integers [b₁,b₂], find a subcollection of these primes whose product lies in the given range.