2 ms·
Actually, this doesn't follow at all (although it is what the article author claims). The exact inverse is true. In the extreme case, where we require no zeros
by CJefferson 12y ago
Actually, this doesn't follow at all (although it is what the article author claims). The exact inverse is true.
In the extreme case, where we require no zeros, the problem is trivial (just hash any old data), and any good SAT solver will finish fairly quickly (perhaps with a little guidance). If we require all zeros, we are effectively asking the solver to break SHA2, which no SAT solver is going to do well at at present, or the forseeable future.
While assigning variables does decrease the worst-case complexity, no number of zeroes can be brute forced by exhaustive search before the heat death of the universe, and assigning zeroes makes finding solutions harder in a search problem which is still massive.