What for does SAT solver needed for package management?

Forum thread started by X512 on Sun, 2012-06-17 15:27

As I understand package resolution in Haiku will be implemented using this. Boolean satisfiability problem is a NP-complete task. So depedency resolution can't be solved in polynomial time. I really don't understand what for does it need.

Package resolution can be implemented like shared object resolution. For example package A requires package B v1.6 and package C v4.3. If you install package A, system will check existness and correct version range for packages B and C. If all is OK then package will be installed successfully, if not, system can request user to download packages or automatically download it from repositiry. I don't see any boolean satisfiability problem or NP-complete tasks. Searching package by name is log(N), enumerating depedencies is M, total is M*log(N).

Can everyone explain where am I wrong?

‹ [HELP] What's the Haiku typical latency ? MATLAB FOR HAIKU ›

Comments

Re: What for does SAT solver needed for package management?

by Diver - 2012-06-17 16:25

Hi, it's probably better to ask this kind of questions on the mailing list or directly Ingo or Oliver. Developers rarely read forum posts.