/* ---- Google Analytics Code Below */

Wednesday, July 26, 2017

Science of Brute Force

A technical point, but with important implications.   Analysts look for Algorithms, or simplified statements of what will be solutions in specific contexts.   These predict.   Algorithms can be a set of math or logical statements, or can be a universal proof of some truth we can apply.  It turns out that some algorithms are best addressed by brute force, or by exploring their context space, by iterating through many, many potential solutions.  This is called 'brute force', and is covered in the most recent issue of the Journal of the CACM, linked to below.   Also see this overview Vimeo presentation.   Technical.

The Science of Brute Force
Many relevant search problems, from artificial intelligence to combinatorics, explore large search spaces to determine the presence or absence of a certain object. These problems are hard due to combinatorial explosion, and have traditionally been called infeasible. The brute-force method, which at least implicitly explores all possibilities, is a general approach to systematically search through such spaces. ... " 

Brute force has long been regarded as suitable only for simple problems. This has changed in the last two decades, due to the progress in Satisfiability (SAT) solving, which by adding brute reason renders brute force into a powerful approach to deal with many problems easily and automatically. Search spaces with far more possibilities than the number of particles in the universe may be completely explored. ... " 

No comments: