hardness.tex 9.54 KB
 Michael Keller committed May 15, 2022 1 \chapter{Computational Difficulty}  Michael Keller committed Apr 19, 2022 2   Michael Keller committed May 15, 2022 3 We prove that the problem of finding a  Michael Keller committed Apr 20, 2022 4 5 solution of a certain quality to a pixel farming problem is NP complete.  Michael Keller committed Apr 19, 2022 6 7 8 9 To do this we will first formulate the problem as a decision problem. In a second step we will show that the problem is in NP. Lastly we will prove that pixel farming can be used to find  Michael Keller committed May 15, 2022 10 Hamiltonian Paths, which will imply that finding  Michael Keller committed Apr 28, 2022 11 solutions for pixel farming is NP complete.  Michael Keller committed Apr 19, 2022 12 13 14  \section{The decision version of pixel farming}  Michael Keller committed May 15, 2022 15 16 We define the decision version of the pixel farming problem very similarly to the  Michael Keller committed Apr 19, 2022 17 18 regular version. However, instead of asking for a field with the maximum score, we ask  Michael Keller committed May 15, 2022 19 for a field with a score of at least $s$. Formally:  Michael Keller committed Apr 19, 2022 20 21 22 23 24 25 Does a field $F$ for relation function $R$ exist such that the score $S(F, R)$ is at least $s$: \begin{displaymath} s \leq S(F, R) \end{displaymath}  Michael Keller committed May 15, 2022 26 \section{Pixel Farming is NP Complete}  Michael Keller committed Apr 20, 2022 27 28 29 30 31 32 33 34 35 36  Now that we have defined the decision version of the problem, we formulate and prove the following theorem: \begin{theorem} The decision version of pixel farming is NP complete. \end{theorem} \begin{proof}  Michael Keller committed Apr 19, 2022 37   Michael Keller committed May 15, 2022 38 First, we non-deterministically select  Michael Keller committed Apr 28, 2022 39 40 a field $F$ for a given relation function $R$. By computing the score $S(F, R)$, which  Michael Keller committed May 15, 2022 41 42 can be done in polynomial time in relation to the field size $X \cdot Y$, we can easily test wether the score  Michael Keller committed Apr 19, 2022 43 44 45 46 47 48 49 is at least a certain value. Further, testing whether our field $F$ meets the requirements specified by $D$, our probability distribution specifying how much of the field should consist of a certain crop, can also be done in polynomial time in relation to the field size $X \cdot Y$ and number of crops $C$.  Michael Keller committed Apr 20, 2022 50   Michael Keller committed Apr 19, 2022 51 It is known that finding Hamiltonian Paths is NP  Michael Keller committed Apr 28, 2022 52 53 complete \cite[Page 199, GT39]{alma990005774300205503}. Thus, reducing the decision version  Michael Keller committed May 15, 2022 54 of Hamiltonian Paths (explained below) to the decision  Michael Keller committed Apr 19, 2022 55 56 57 58 59 version of pixel farming demonstrates that pixel farming is NP complete. \paragraph{Hamiltonian Paths} Let $G = (V, E)$ be an undirected graph. We formulate the  Michael Keller committed May 15, 2022 60 61 62 decision version of the Hamiltonian Path problem as follows: Does a path that visits every vertex in the graph exactly once exist?  Michael Keller committed Apr 19, 2022 63   Michael Keller committed Apr 28, 2022 64 65 \paragraph{Reduction} We assume we are given an undirected graph $G$ and a polynomial time algorithm in $X \cdot Y$  Michael Keller committed Apr 19, 2022 66 67 68 69 and $C$ for the pixel farming decision problem. We are asked to solve the hamiltonian path decision problem in polynomial time in relation to the size of $G$.  Michael Keller committed Apr 20, 2022 70 71 The core idea is that we translate vertices to crops and edges to crops liking each other. Then, a pixel farming  Michael Keller committed Apr 28, 2022 72 73 decision problem on a $1 \times \abs{V}$ field with a score that means every pixel  Michael Keller committed Apr 20, 2022 74 75 76 77 78 79 80 81 82 83 84 85 likes both of its neighbors must imply that there exists a hamiltonian path in the graph $G$. Formally we build the following pixel farming decision problem: \begin{align*} X &= \abs{V} && Y = 1\\ \Cps &= V && R(a, b) = \begin{cases} 1 & \{a, b\} \in E\\ 0 & otherwise. \end{cases}\\ s &= 2 \cdot (\abs{V} - 1) && D(c) = \frac{1}{\abs{V}} \quad \forall c \in \Cps \end{align*} The following example illustrates this:  Michael Keller committed Apr 28, 2022 86 \FloatBarrier  Michael Keller committed Apr 20, 2022 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 \begin{figure}[h] \centering \begin{minipage}{0.45\textwidth} \centering \begin{tikzpicture}[node distance={15mm}, main/.style = {draw, circle}] \node[main] (1) {$v_1$}; \node[main] (2) [right of=1] {$v_2$}; \node[main] (3) [below of=2] {$v_3$}; \node[main] (4) [below of=1] {$v_4$}; \draw (1) -- (2); \draw (2) -- (4); \draw (3) -- (1); \draw (4) -- (3); \end{tikzpicture} \caption{example graph} \end{minipage}\hfill \begin{minipage}{0.45\textwidth} \centering \begin{tikzpicture}[node distance={0.75cm}, main/.style = {draw, minimum size=0.75cm}] \node[main] (1) {$v_1$}; \node[main] (2) [right of=1] {$v_2$}; \node[main] (3) [right of=2] {$v_4$}; \node[main] (4) [right of=3] {$v_3$}; \end{tikzpicture} \hfill \caption{corresponding solution field} \end{minipage} \end{figure} \FloatBarrier  Michael Keller committed Apr 28, 2022 116 117 118 119 120 It should be noted that is problem can be built in polynomial time in relation to the field size and number of crops $C$. Now we pass the pixel farming problem formulated above to our algorithm that solves the decision version of the pixel farming problem.  Michael Keller committed Apr 28, 2022 121 If we get the answer that no solution  Michael Keller committed May 15, 2022 122 123 124 with value at least $s$ exists, we conclude that no longest path of length $\abs{V} - 1$ exists. If, on the other hand, a solution of at least $s$ exists, we know that a hamiltonian path  Michael Keller committed Apr 28, 2022 125 126 must exist in $G$.  Michael Keller committed May 15, 2022 127 The rationale for this is as follows: Let us assume  Michael Keller committed Apr 28, 2022 128 129 130 a solution of value at least $s$ exists. This would imply that every pixel likes all of their neighbors. As "crop $a$ likes crop $b$" is the same function as  Michael Keller committed Apr 28, 2022 131 132 "vertex $a$ is connected to vertex $b$", we must have found $\abs{V}-1$ edges that connect our $\abs{V}$ vertices. Because we also  Michael Keller committed Apr 28, 2022 133 134 135 136 know that every crop can only appear once in our field and all crops have two neighbors (except the ends) we must have found a path of length $\abs{V} - 1$.  Michael Keller committed May 15, 2022 137 If, on the other hand, no arrangement of value at least $s$  Michael Keller committed Apr 28, 2022 138 139 140 141 142 exists, there must be at least one index $i$ for all fields $F$ where $R(F_{1, i}, F_{1, i+1}) = 0$. What this translates to for our longest path problem is that every order of vertices has an index $i$ where $\{v_i, v_{i+1}\} \not \in E$, hence no path of length $\abs{V} - 1$ can exist.  Michael Keller committed Apr 20, 2022 143   Michael Keller committed Apr 28, 2022 144 145 As we now know that pixel farming is in NP and NP-hard, we can conclude that pixel farming must be NP-complete.  Michael Keller committed May 11, 2022 146 147 \end{proof}  Michael Keller committed May 15, 2022 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 % \section{Fractional Pixel Farming is NP Complete} % We consider the slightly modified version of the % standard pixel farming decision problem. Instead of allowing % a pixel to only contain a single crop, % a pixel may now contain multiple crops, as explained % in the problem definition section. One might suspect that % such a relaxation might enable us to formulate a % convex optimization problem. We show however that % this relaxation is also NP complete. % We define the decision version of fractional pixel farming % analogously to the standard version: Does a field $F'$ % for a relation function $R$ exist such that the score % $S(F', R)$ is at least $s$: % \begin{align*} % s \leq S(F', R) % \end{align*} % \begin{theorem} % The fractional pixel farming problem (decision version) is NP complete. % \end{theorem} % \begin{proof} % The problem is obviously in NP, as we can non-deterministically % choose a field $F'$ for a given score function % $R$ and calculate the % score in polynomial time in relation to the size of the % field and number of crops. In a next step we verify % that the solution meets the requirement for crop % distribution given to us. This can also be done in % polynomial time relative to field size and number % of crop types. Finally, we test if the score $S(F', R)$ % is at least $s$. % For the proof of NP Hardness we again reduce to the % Hamiltonian Paths problem as in the proof that % regular pixel farming is NP complete. For this % purpose we define the constructed pixel farming % problem for a given graph $G = (V, E)$ as follows: % \begin{align*} % X &= \abs{V} && Y = 1\\ % \Cps &= V && R(a, b) = \begin{cases} % 1 & \{a, b\} \in E\\ % 0 & otherwise. % \end{cases}\\ % s &= 2 \cdot (\abs{V} - 1) && D(c) = \frac{1}{\abs{V}} \quad \forall c \in \Cps\\ % F' &\in R_+^{C \times X \times Y} % \end{align*} % We show that % the following implications hold: % \begin{enumerate} % \item There exists no optimal fractional solution to % the constructed pixel farming problem $\implies$ % There exists no Hamiltonian path in $G$ % \item There exists an optimal fractional % solution to the constructed pixel farming problem % $\implies$ There exists a Hamiltonian path in $G$ % \end{enumerate} % % The first implication is obviously true. We prove this indirectly, % that is we show that: There exists a hamiltonian path in $G$'' % $\implies$ There exists an optimal fractional solution to the % constructed pixel farming problem''. This statement is a % direct consequence of the NP completeness proof for the standard % pixel farming problem. If a Hamiltonian path exists, then % an optimal solution for the standard pixel farming problem % instance exists. As this standard solution can also be % viewed as an optimal fractional solution ($1$'s and $0$'s % are fractions too) we are done. % The second implication we prove by directly. % We assume that there exists an optimal solution to the % constructed pixel farming problem for a % Graph $G$. An optimal % solution in our case means that every crop likes % all of the crops in its neighborhood, otherwise % the solution would not obtain the maximal % possible score $s$. Further there must also % exist a sequence of crops such that: % \FloatBarrier % \begin{enumerate} % \item The sequence only contains each crop exactly once % \item Every pixel along the proposed sequence of crops contains some of the proposed crop % \end{enumerate} % \FloatBarrier % If these two facts did not hold, then there must % exist a crop within our valid solution that is contained % less than once, which would mean our solution is invalid. % TODO: MAKE MORE FORMAL % As a sequence of all crops where every crop % likes its neighbors corresponds to $G$ % containing a hamiltonian path, we know % our statement must be true. % \end{proof}