2 ms·
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 co
by qznc 9y 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.
- petroseskinder 9y agoThat's fair. Whenever I think of dependencies, I imagine conflicts are fair game.
- qznc 9y agoWhy? 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.