Let $x_i$ where $i = 1 \cdots n$ be the boolean variables meaning package $i$ is installed. The system contains $p$ equations such as "at least" $x_i \cup x_j = true$ or "dependent on" $-x_i \cup x_ j = true$ or "incompatible" $- x_i \cup - x_j = true$

To solve, one can try all the $2^n$ possibility to see whether they satisfy the system or not. The calculation amount is $2^n p$

(a) When solving this system, set a boolean value to $x_i$ , an equation related to $x_i$ must be either dummy true or implying the other variable $x_j$ to be a specific boolean value. For case of dummy true, simply this equation is removed from the system for further simpler system. For case of "implying the other variable", put the decision info by an arrow in the graph:

For $x_1 \cup x_2 = true$ , it is

For $- x_1 \cup x_2 = true$ , it is

For $- x_1 \cup - x_2 = true$ , it is

(b) said in (a) already ( c) It is like spread of 殭屍病毒. Starting from a single node, it spreads and infects all nodes by the graph above. So a feasible configuration must be a collection of a connected area. Take an example, package $2i-1$ is only relevant to package $2i$ by the "at least" equation so a feasible configuration is like:

And every arrow is the only arrow in a connected area

But note that an occupying area in a connected is not necessarily feasible. It is possible an and an

and an conclude to some $x_i$ is both true and false, obvious an infeasibility.

(d) Beside the trivial algorithm mentioned above. It is possible to structure the algorithm recursively by leading a system of $n$ variables and $p$ equations to a smaller system of $n'$ variables and $p'$ equations where $n' < n$ and $p' < p$ . In fact, this algorithm is the same spirit when one tries to solve a system like substitution of variables taught in middle school about linear system. Internal in the algorithm, one must make use of the graph or equivalent construct to conduct the "reduction of the system"

( e) The both algorithms, this one in (d) and the trivial one mentioned before (a), must be correct. What else it could be?

(f) The simple trivial algorithm is $2^n p$ . For the recursive one, let $f(n,p)$ denote the computation size, then by its recursive structure, it is where $f(n, p) = p + f(n', p') + f(n'', p'') \approx p +   f(n', p')n'< n, p'< p, n''< n, p''< p$ and $p f(n',p')$ is for trying setting some variable to be true and $p f(n'',p'')$ is for trying setting this variable to be false. When one of the $n$ or $p$ arguments of the function reaches zero, it is the base case. Therefore, for worst case it is :

$\begin{aligned}f(n,p) = p + 2 f(n - 1 , p - 1) = p + 2 \left(p - 1 + 2 f(n - 2 , p - 2) \right) = p + 2 (p - 1) + 4 f(n - 2 , p - 2) \\= p + 2 (p - 1) + 4 \left(p - 2 + 2 f(n - 3 , p - 3) \right)= p + 2 (p - 1) + 4 (p - 2) + 8f(n - 3 , p - 3) = \cdots \end{aligned}$

So the size is $p + 2(p - 1) + 4 (p - 2) + 8 (p - 3) + \cdots$ total $min(n,p)$ terms aka, where $$\begin{aligned}a = 2p + 2 (p - 1) + 4 (p - 2) + 8 (p - 3) + \cdots = p (1 + 2 + 4 + \cdots -\sum_{i = 0}^{min(n , p) - 1} 2^i i\\= p (2^{min(n, p)}-1)-\sum_{i=0}^{min(n,p)-1} a^i i\end{aligned}$[latex=

$\begin{aligned}\sum_{i=0}^{min(n,p)-1} a^i i = a \sum_{i=0}^{min(n,p)-1} a^{i-1}i = a \sum_{i=0}^{min(n,p)-1} \frac{d a^i}{d a} = a \frac{d}{d a}\left(\sum_{i=0}^{min(n,p)-1} a^i \right)= a \frac{d}{d a}\left(\frac{a^{min(n,p)}-1}{a - 1}\right) \\= a \frac{min(n,p) a^{min(n,p)-1}(a - 1) - ( a^{min(n,p)} - 1 )}{(a - 1)^2} = 2\left({min(n,p)} 2^{min(n,p)-1} - (2^{min(n,p)}-1)\right)\end{aligned}$

So the overall work size is $(p + 2)(2^{min(n,p)}-1) - min(n,p) 2^{min(n,p)} = (p + 2 - min(n,p)) 2^{min(n,p)} - (p + 2)$