Tags: category h


How do we know the Borg has discovered room temperature superconductors?

I think I have a proof that the scale balancing problem (find two subsets of two sets of integers, one each, so that their sums are equivalent) is NP-complete even when the sets are superincreasing.

As for the subject, it's trivial: "Resistance is futile".

[EDIT: I think a reduction from NAND CVP to SUPERINCREASING KNAPSACK somehow utilizes the boolean properties of binary addition (with carries or without) to create a equivalence of the sort "if there exists a sum that has the last bit as 0 then the output of the circuit, encoded as integers, is false". I don't know the details though, but it may help others, if anyone is reading this.]