\myheading{Ubuntu Linux}

Many Ubuntu Linux users see this often:

\begin{lstlisting}
% sudo apt install katomic
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
  a2jmidid libsamplerate0:i386 pulseaudio-module-jack python3-cffi python3-jack-client python3-ply python3-pycparser qasmixer
  qastools-common zita-ajbridge
Use 'sudo apt autoremove' to remove them.
The following additional packages will be installed:
  kdoctools5 khelpcenter libgrantlee-templates5 libkf5kdegames-data libkf5kdegames7 libkf5newstuff-data libkf5newstuff5
  libkf5newstuffcore5 qml-module-org-kde-newstuff
The following NEW packages will be installed:
  katomic kdoctools5 khelpcenter libgrantlee-templates5 libkf5kdegames-data libkf5kdegames7 libkf5newstuff-data libkf5newstuff5
  libkf5newstuffcore5 qml-module-org-kde-newstuff
0 upgraded, 10 newly installed, 0 to remove and 20 not upgraded.
Need to get 7,175 kB of archives.
After this operation, 28.3 MB of additional disk space will be used.
Do you want to continue? [Y/n]
\end{lstlisting}

During installation of a package, other packages are to be installed - libraries, optional packages, etc.
Also, 'apt' utility tries to find the most fresh packages.

How an Ubuntu package is defined?

\begin{lstlisting}
Format: 3.0 (quilt)
Source: katomic
Binary: katomic
Architecture: any
Version: 4:20.08.0-1
...
Build-Depends: cmake (>= 3.5~), debhelper-compat (= 13), extra-cmake-modules (>= 5.30.0~), gettext, libkf5config-dev (>= 5.30.0~), libkf5coreaddons-dev (>= 5.30.0~), libkf5crash-dev (>= 5.30.0~), libkf5dbusaddons-dev (>= 5.30.0~), libkf5doctools-dev (>= 5.30.0~), libkf5i18n-dev (>= 5.30.0~), libkf5kdegames-dev (>= 4.9.0~), libkf5newstuff-dev (>= 5.30.0~), libkf5widgetsaddons-dev (>= 5.30.0~), libkf5xmlgui-dev (>= 5.30.0~), pkg-kde-tools (>> 0.15.15), qtbase5-dev (>= 5.7.0~)
Package-List:
 katomic deb games optional arch=any
...
\end{lstlisting}
( \href{http://mirrors.edge.kernel.org/ubuntu/pool/universe/k/katomic/katomic_20.08.0-1.dsc}{src} )

Here you see that the 'katomic' package requires the 'debhelper-compat' package of exact version 13, 'pkg-kde-tools' newer than
version 0.15.15, 'gettext' package of unspecific version, etc...

More on .dsc files file format:
\href{https://www.debian.org/doc/debian-policy/ch-relationships.html}{1},
\href{https://www.debian.org/doc/debian-policy/ch-controlfields}{2},
\href{https://www.debian.org/doc/manuals/debmake-doc/ch05.en.html}{3},
\href{https://www.debian.org/doc/manuals/maint-guide/dreq}{4}.

Almost all Linux distributions has some kind of this system.
Haskell has 'Cabal' system \href{https://github.com/elben/sat/blob/master/sat.cabal}{example package}.

This task is a good specimen of \ac{CSP}, which is NP-problem, of course.