3 ms·
> What if I develop simple statistical models based on the number of squares that are already filled in? What if you were unable to? NP-hard problems are weird
by zeteo 13y ago
> What if I develop simple statistical models based on the number of squares that are already filled in?
What if you were unable to? NP-hard problems are weird like that. What if the underlying statistical distribution had random variance or some other strange features that make traditional statistical models useless?
Maybe the issue is that we're trying to use intuitions developed with everyday problems that are essentially linear ("mow the lawn", "drive to the store") in places where they're not appropriate. Unlike usual everyday tasks, NP-hard problems (such as Sudoku or coding) have no known "royal road" - sometimes you just have to try all possible solutions.
- jacques_chester 13y agoNP-hard problems often have "good enough" solutions that don't take heat-death time to solve. Consider the TSP. You can wait until the last proton decays and tie up all matter and energy in the universe. Or you can use an ant colony optimiser and accept that you will probably only come to within a few percent of the best possible solution. Oh noes! And so it is with estimation. We can build an ever-more-elaborate estimate that will consecutively shave fractions of a percentage point of precision and accuracy. Or we can accept that they are estimates, that they are meant to be imprecise and that accuracy is a range, not a number.