Precise definition of a brute force algorithm

Question

What is the precise definition of a brute force algorithm?

Is it one that simply has non-polynomial runtime?

• D.W.: What research have you done? Can you summarize what you have found so far, in the question? I suggest starting with standard textbooks, Wikipedia, and a Google search. See, e.g., en.wikipedia.org/wiki/Brute-force_search. There is not much point in us repeating material that is already found in widely-available resources, like Wikipedia.

Answer 1

Consider any optimization or decision problem $P$. A brute-force algorithm $A$ for $P$ is the one that considers all possible valid arrangements or assignments of the input to determine the optimum value or its feasibility. Formally, a brute-force algorithm evaluates (in the worst case) all possible candidates in the solution space to determine the optimum or decide the feasibility of the input.

[[Example 1]] Consider the Traveling Salesman Problem (TSP), whose input is a graph $G=(V,E)$ with some cost assigned to the edges. A brute-force algorithm can be the one that considers all permutations of the node in $V$ and finds the optimal one.

[[Example 2]] Consider the Satisfiability Problem (SAT), whose input is a boolean formula $\phi$ involving $n$ variables. A brute-force approach can be to consider all 2ドル^n$ assignments of the variables to determine the feasibility of $\phi$.

• Geremia: I'm glad you mentioned SAT. Since any algorithm can be transformed into SAT, it seems brute force could be defined as an algorithm with $\mathcal O(2^n)$ time complexity, where $n$ = number of SAT vars required to represent the algorithm.
• codeR: Complexity would depend on the problem. For the TSP problem on a $n$ vertex graph, your brute-force algorithm may explore all $O(n!)$ permutations.

Answer 2

It's on a scale - how much cleverness did you employ in your algorithm.

There is one level where your algorithm is plain stupid. For example, sort an array by rearranging all items randomly, then checking whether it is sorted, until it is sorted. That's not even brute force, that's stupid.

When your algorithm is improved to do nothing stupid, then you can call it "brute force".

And from then on you can apply any number of improvements until it is not called brute force anymore. It depends on your experience. If you only apply improvements that are obvious to you then you can still call it "brute force". To a software developer with much less or much more experience it might be highly optimised or still stupid.