jeffgerickson / algorithms

Bug-tracking for Jeff's algorithms book, notes, etc.
7.95k stars 1.02k forks source link

Fix the imprecise definition of the circuit satisfiability problem #250

Open rudolf-adamkovic opened 3 years ago

rudolf-adamkovic commented 3 years ago

NP-hardness:

Given a boolean circuit, is there a set of inputs that makes the circuit output True, or conversely, whether the circuit always outputs False.

Given a boolean circuit, is there a non-empty set of inputs that makes the circuit output True, or conversely, whether the circuit always outputs False.

Or drop the word "set" and say "are there any inputs".

rudolf-adamkovic commented 3 years ago

Actually, on a second thought, if the "set of inputs" means the collection of signals that enter the circuit at the same time, then my suggestion is incorrect. Still, those inputs are not a set, as the input values that correspond to specific "input lines". Either way, the word "set" confuses the reader, I think.