3 ms·
Actually I'm not sure that claim is accurate (they state it as an intuition). The fact that there are more constraints (that was the word you're looking for) do
by scscsc 12y ago
Actually I'm not sure that claim is accurate (they state it as an intuition). The fact that there are more constraints (that was the word you're looking for) does not necessarily mean that SAT will be easier. It could be that the constraints make finding a solution more difficult.
- ITwitchToo 12y agoIt is true in an absolute, mathematical sense that the search space gets smaller when you fix a variable to a particular value. However, by fixing a variable (and effectively removing it), you are also removing potential solutions from that search space. In a sense, you could view the difficulty of a SAT problem as the fraction of valid solutions in the whole search space. By fixing a variable, you are decreasing both the number of valid solutions and the size of the total search space. But the fraction could end up being either greater or smaller, depending on the variable and the value you set it to.
- semiel 12y agoThe constraints will definitely make finding a solution more difficult. If not, Bitcoin hash difficulty would be totally broken. The question is what the _rate_ of difficulty increase is like, compared to the brute force approach.