NAND CIRCUIT COLLISION: Given two NAND circuits, does there exist some set
of two inputs so that the first input when given to the first circuit produces
the same output as the second input given to the second circuit?
NPcomplete. Reduction from an arbitrary NPcomplete problem:
For the first NAND circuit, create one that outputs "true" for any
input.
For the second NAND circuit, create a verificator for the decision
version of whatever NPcomplete problem. That is, given an input,
it verifies it, (e.g input a weight and a subset for knapsack, or
a CNF formula and a set of assignments for CNFSAT), and returns
true if the input is correct, false if not.
Now because the first always returns true, and the second returns true
only if there is a solution to the problem in question, then this
setup will return true iff the problem is feasible, and since the
problem is NPcomplete, so is finding out if it is feasible.

Now, if we can show that any and all instances of the NAND CIRCUIT VALUE
PROBLEM can be transformed to SUPERINCREASING KNAPSACK, by the above,
SUPERINCREASING KNAPSACK COLLISION (the "scale balancing problem") is shown to
be NPcomplete. As both NAND CIRCUIT VALUE and SUPERINCREASING KNAPSACK is
Pcomplete, this should be possible.
http://www.i.kyushuu.ac.jp/~shoudai/Pcomplete/all/node7.html
http://www.i.kyushuu.ac.jp/~shoudai/Pcomplete/all/node51.html