If we only consider the search effort needed to find an optimal solution (not taking into account the work needed to provide a certificate of optimality by ruling out closer strings at lower distance) then the speedup of PWM over smallest domain is at the level of orders of magnitude in the general case - Figure 2, lower panel. This indicates that heuristics are less important when searching exhaustively at a lower than optimal distance: most of the practical complexity of closest string search is associated with providing certificates of optimality, rather than identifying close strings which turn out to be optimal.

![0_image_0.png](0_image_0.png)

Figure 3 shows that we achieve a good approximation very quickly, in line with existing results that guarantee approximation to four thirds of optimality in polynomial time [14, 16]. This motivates the hybrid symbolic-numeric methods detailed in Section 3.4: practitioners can use CSP to obtain good bounds quickly, then use either numeric methods or AI search methods - or indeed both using a distributed architecture - to explore the remaining search space for an exact solution plus certificate of optimality.

Taken together the results indicate that:

1. CSP search with PWM variable-value ordering will (in general) efficiently find candidate solutions to closest string problems with decreasing maximum distance d 2. CSP search with any sensible search ordering can be used to exhaustively rule out the distance below the optimal d 3. our empirical evidence is in line with previously reported results: an approximate solution to closest string can be computed in polynomial time, but computation of the necessary certificates of optimality remains intractable in the general case 4. sequential, single-processor CSP search for problems having more strings of greater length (and possibly a larger alphabet) will become intractable due to the inherent NP-completeness of closest string.