WLOG

WLOG is mathematics-speak for 'without loss of generality', which means 'restricting ourselves to considering a special case, which is not really a restriction'. For example, is there a drive from Berkeley to Las Vegas that's less than 500 miles? WLOG we can look for one that doesn't involve visiting any one spot twice.

The above example illustrates two features of WLOG claims:

i) They are frequently commonsensical observations;

ii) They can eliminate a great deal of dross very easily, making efficient algorithms possible.

Using dynamic programming to solve construction problems is a prime example. Here we have construction tasks where the 'worth' of a partial solution can be completely summarized with a few well-chosen parameters; if two competing partial solutions have the same parameters, we can WLOG throw one of them away.

So, in our example, our idealized travel problem has length and stopping point as the sole relevant parameters for partial trips: if we think the shortest trip to Vegas might take us through Reno, and we've found two equally short shortest-paths to Reno, WLOG we can flip a coin and store only the winning path as we try to extend it from Reno to Vegas. Of course, we also need to consider paths that don't pass thru Reno (which, as it turns out, is way too far north).

Note that, while the no-looping-paths restriction has a distinct preference when it makes restrictions, this second dynamic-programming restriction has a symmetric character--indifferent to which candidate it keeps--and is motivated purely by a desire to reduce the size of our search space and save computation time. Both types of restriction are common.

As a challenge, try to apply domain-specific WLOG-reasoning to give a solution (not necessarily efficient) to the following geometry problem:

Circle Packing: Given a set of circles of rational radii r_1, r_2, ... r_n > 0, and the dimensions of a rectangle R, can the circles be packed into R without overlap or dissection?

Probably an old problem, and close to NP-complete problems if not NP-complete itself (?), but I cribbed it from this book which, although insubstantial, I recommend skimming for puzzles.