Tags: category h

Dwight

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.]