The world of search problems is a bleak landscape. There are a few bright spots — brilliant algorithmic ideas — each illuminating a small area around it. These areas are the problems that reduce to it, and two such areas, linear and dynamic programming, are in fact quite decently large. But the remaining expanse is pitch dark, $\mathbf{NP}$-complete.
When solving a problem with graphs and numbers, what do you do? Assuming none of our usual techniques (LP, DP, shortest paths etc.) work, you could prove your suspicions that it is not solvable first by proving that such a problem is $\mathbf{NP}$-complete.
But the problem does not go away when proved $\mathbf{NP}$-complete. What do you do next? This is the subject of some of the most important modern research on algorithms and complexity. $\mathbf{NP}$-completeness does not spell a death sentence. We proved in some earlier sections that certain subproblems, like Independent Set, can be solved in linear time by techniques such as dynamic programming.
Often, you cannot neatly characterize the instances that come up in your application, and instead, you will have to rely on some form of intelligent exponential search — procedures such as backtracking and branch-and-bound are exponential time in the worst-case, but with the right design, could be very efficient on typical instances.
Or you could design an algorithm that falls short of the optimum, but never by too much, called an approximation algorithm. In Set Cover, we saw a greedy algorithm that always produces a set cover no more than $\log{n}$ times the optimal set cover.
And finally, there are heuristics, algorithms without a guarantee on either running time nor degree of approximation. They rely on ingenuity, intuition, a good understanding of the application, experimentation, and often insights from science, to attack a problem.
<aside> 💡 Backtracking is technique based on the observation that it is often possible to reject a solution by looking at just a small portion of it.
</aside>
An example would be in SAT. If an instance of SAT contains the clause $(x_1\vee x_2)$, then all assignments with $x_1=x_2=0$ can be instantly eliminated. To put it differently, by quickly checking and discrediting this partial assignment, we are able to prune q aurter of the entire search space. Can we systematically exploit this?
Consider the Boolean formula $\phi(w,x,y,z)$ specified by the set of clauses
$$ (w\vee x\vee y\vee z),(w\vee\bar{x}), (x\vee\bar{y}), (y\vee\bar{z}), (z\vee\bar{w}), (w\vee\bar{z}) $$
We will incrementally grow a tree of partial solutions by first branching on any one variable, say $w$:
Plugging $w=0$ and $w=1$ into $\phi$, we find that no clause is immediately violated, and neither partial assignment can be eliminated outright. Let's expand one of the two available nodes on a variable of our choice:
This time, we are in luck. The partial assignment $w=0, x=1$ violates the clause $(w\vee\bar{x})$ and can be terminated, thereby pruning a good chunk of the search space. We now backtrack out of this cul-de-sac, and continue our explorations at one of the two remaining active nodes.
In this manner, backtracking explores the space of assignments, growing the tree only at nodes where there is uncertainty about the outcome, and stopping if at any stage, a satisfying assignment is encountered.
In the case of Boolean satisfiability, each node of the search tree can be described by either a partial assignment, or by the clauses that remain when those values are plugged into the original formula. For instance, if $w=0$ and $x=0$, any clause with $\bar{w}$ or $\bar{x}$ is immediately satisfied, and any literal $w$ or $x$ is not satisfied and can be removed. What's left?