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?

NP-complete. Reduction from an arbitrary NP-complete 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 NP-complete 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 CNF-SAT), 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 NP-complete, 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 NP-complete. As both NAND CIRCUIT VALUE and SUPERINCREASING KNAPSACK is
P-complete, this should be possible.

	http://www.i.kyushu-u.ac.jp/~shoudai/P-complete/all/node7.html
	http://www.i.kyushu-u.ac.jp/~shoudai/P-complete/all/node51.html