What is (Re:) NP-Completeness?

[Jesse Glick]

On 12/23/2011 10:07 AM, Richard S. Hall wrote:
> if Jesse can modify his sample to create an reasonably realistic example (i.e., something you are likely to see in the wild)

I doubt it. The crux of the translation to 3-SAT, and of the choice of hard 3-SAT problems, is that the "clause" modules fi appear in multiple (three) releases, yet show 
a pathological usage of the "variable" modules vi: f5 @ 1 might require v9 @ 1 while f5 @ 2 requires v9 @ 0. To decide whether to use f5 @ 1 or @ 2 you need to figure out 
how v9 is used by other fi, but picking one of these can screw up the choice of a different vi used by f5, leading to near-endless backtracking.

In practice you would rarely start to use an _older_ version of some library in a new release of your own module. It can happen - e.g. due to regressions discovered in 
the library and not yet fixed in a patch update - but perhaps not often enough to break heuristic solvers. When dependencies are only ever upgraded, I am guessing that a 
polynomial resolution algorithm exists (proof or contradiction welcome!), though enforcing such a policy would probably be unacceptable anyway.