[krageon]

Anything over "basically none" is absurd, but in this case the worst case really is very bad.

[bdg]

How would you solve it with very little computing resources? I've yet to see any reasonable solution.

[ecnahc515]

There's a few novel techniques such as minimal version selection: https://research.swtch.com/vgo-mvs. I know I've seen a few others in the past years but I'm struggling to remember which ones are non-SAT solving approaches.