Not very the parts that make it NP hard are allowing libraries to specify maximum versions (and other more complex version ranges). Most of the time libraries use minimum constraints (~) or (^) which allows the heuristic to work like go's algorithm. For rust, node, and other languages libraries can be imported twice as different versions (without requiring a major version renaming like go) this also allows the heuristic to have an out: if it reaches a really complex case it can just give you both versions. Beyond that package management is a barely disguised 3-SAT solver which we have good, fast solvers. There are definitely some edge cases, but when's the last time you ran any of the following package managers and worried about dependency solve speed? cargo, apt-get, npm (and yarn), dnf, zypper. IO far and away dominates the profiles of these programs, solver speed is basically a non-issue in practice.

depends on the complexity. if it is 2^1000 then forget about finding an optimal result.

The counterarguments are, basically:

1. vgo focuses on the wrong issue (if you're spending a ton of time resolving and re-resolving your dependency graph, maybe the issue is your build process).

2. vgo will get the wrong answers and/or make development much harder

There's a long writeup of some of the ways vgo can go wrong here: https://sdboyer.io/vgo/failure-modes/ and some background here: https://sdboyer.io/vgo/intro/ among other places. And there was a lot of discussion here: https://news.ycombinator.com/item?id=17183101

I'd say there's about a 3% chance vgo ends up being a smashing success that revolutionises package management and gets copied by everyone else, a 30% chance that vgo works well for golang due to their unique requirements but has nothing to offer anyone else, and about a 67% chance it ends up being a failure and being scrapped or heavily revised to scrap the novel, controversial and (arguably) fundamentally broken ideas that set it apart from every other package manager.

But fundamentally, the reason the cargo people aren't copying it right now is that it doesn't even really claim to have advantages over cargo for rust. (There are some quirks in the golang ecosystem which mean you end up analyzing your dependency tree way, way, more than you do in basically any other common language. That makes speed important for golang, but for everyone else, it's almost meaningless.) "We make the unimportant stuff fast at the expense of getting the importing stuff wrong" isn't very compelling. :)

Of course, the vgo people would phrase it as "we make the important stuff fast and we get the important stuff right", so...time will tell. But don't expect anyone to copy this quickly; it remains to be seen if it'll even work for golang, and it'd need to be a huge step up from the current state of the art to make it worth switching for other languages and ecosystems.

The catch to the vgo approach required that no package in the ecosystem ever have even unintentional backwards incompatibilities, because you can't do anything other than specify minimum versions. Or, rather, it makes the resulting problems something that need to be addressed outside the scope of dependency specification and resolution.

When you just decide not to address a significant part of the problem, the solution becomes simpler.

I’m no expert, and I might even be very wrong, but I read the post about it and it seems to hinge on only resolving a minimum version and assuming all future packages with the same import path are backwards compatible. If I’m reading right it basically treats path/to/package and path/to/package/v2 as entiresly different packages.

As a rule, Rust and Cargo developers aren't satisfied with something until it's difficult to explain and complicated to implement.