Hacker News new | ask | show | jobs
by qznc 3189 days ago
It is NP complete, if conflicts are possible. Is that what Molinillo means by a 'locking' dependency graph?

If conflicts are not possible, then it is not NP complete, toposort is good enough, and backtracking is unnecessary.
1 comments
petroseskinder 3188 days ago
That's fair. Whenever I think of dependencies, I imagine conflicts are fair game.
link
qznc 3188 days ago
Why? In Debian conflicts are usually only used to remove obsolete software from old releases.

Conflicts between packages which are both maintained should not happen. If two packages want to provide the same file, Debian can install both and has tooling to switch between them.

link