Is there a mathematical explanation for why problems have algorithms that are better than brute force? It feels like we have to take advantage of some type of order that could help us identify smaller recurring subproblems or help us eliminate possibilities with a single step. Does it have something to do with a fundamental order like a mapping to natural numbers?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I don't think there is much good reasoning for why some algorithms are better than a brute force.
If I'm remembering correctly, brute-force is more of an informal term we use to describe some algorithms (usually meaning to try every different possible combination). But it's not a pure math term, with a mathematical basis.
Compared to the complexity classes, we have, where you'll likely find both exponential time brute-force algorithms, and polynomial time brute-force algorithms.
Though you will find most algorithms abuse some properties, such as the one's you've mentioned, to make it faster than trying out every combination possible, which helps eliminate other possibilities. Mathematically though, even a breadth first search could be considered a form of brute-force on a subset of possible pathways that lead us to the shortest path in an undirected and unweighed graph.
This can especially be noticed with some problems, where the algorithm might be an O(N^2) solution, but still very much feel like it's a brute-force.
One really good example of this is the knapsack problem. The knapsack problem informally is O(N^2), and it's the smart dynamic programming approach. But it's still technically a brute-force. This is because we've figured out how to formulate the best answer as a recursive formula, but using Dynamic Programming, we just know that there are repeated cases which do not need to be re-calculated over and over again.
Knapsack mathematically is an NP-Complete problem, but it's still N^2. Which just goes to show, we really don't have great reasoning yet for why an algorithm may be better than a brute-force.
I think actually, this entire concept relates to whether P = NP, and therefore there is probably no good mathematical answer that exists at the moment. (As P = NP is an unsolved problem in Computer Science)
