hardness.tex 9.36 KB
 Michael Keller committed Apr 19, 2022 1 2 \chapter{Computational Hardness}  Michael Keller committed Apr 20, 2022 3 4 5 We show that the problem of finding a solution of a certain quality to a pixel farming problem is NP complete.  Michael Keller committed Apr 19, 2022 6 7 8 9 10 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 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 15 16 17 18 19 20 21 22 23 24 25  \section{The decision version of pixel farming} The decision version of the pixel farming problem we define very similarly to the regular version. However, instead of asking for a field with the maximum score, we ask for a field with a score at least $s$. Formally: 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 Apr 20, 2022 26 27 28 29 30 31 32 33 34 35 36 \section{Pixel Farming is NP complete} 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 Apr 28, 2022 38 39 40 First we non-deterministically select a field $F$ for a given relation function $R$. By computing the score $S(F, R)$, which  Michael Keller committed Apr 19, 2022 41 42 43 44 45 46 47 48 49 can be done in Polynomial time in relation to the field size $X \cdot Y$, we can easily test is the score 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 Apr 19, 2022 54 55 56 57 58 59 60 of hamiltonian paths (explained below) to the decision 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 decision version of the hamiltonian path problem as follows:  Michael Keller committed Apr 28, 2022 61 62 Does there exist a path that visits every vertex in the graph exactly once?  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 Apr 28, 2022 122 with value at least $s$ exists, we return that no longest path of  Michael Keller committed Apr 28, 2022 123 124 125 126 127 128 129 130 length $\abs{V} - 1$ exists. If on the other hand a solution of at least $s$ exists, we return that a hamiltonian path must exist in $G$. The rationale for this is as follows. Let us assume 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 137 138 139 140 141 142 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$. If on the other hand no arrangement of value at least $s$ 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  \section{Fractional Pixel Farming is NP Complete}  Michael Keller committed May 11, 2022 148 149 We consider the slightly modified version of the standard pixel farming decision problem. Instead of allowing  Michael Keller committed May 11, 2022 150 a pixel to only contain a single crop,  Michael Keller committed May 11, 2022 151 152 a pixel may now contain multiple crops, as explained in the problem definition section. One might suspect that  Michael Keller committed May 11, 2022 153 154 155 156 such a relaxation might enable us to formulate a convex optimization problem. We show however that this relaxation is also NP complete.  Michael Keller committed May 11, 2022 157 We define the decision version of fractional pixel farming  Michael Keller committed May 13, 2022 158 analogously to the standard version: Does a field $F'$  Michael Keller committed May 11, 2022 159 160 161 162 163 164 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*}  Michael Keller committed May 11, 2022 165 166 167 168 169 \begin{theorem} The fractional pixel farming problem (decision version) is NP complete. \end{theorem} \begin{proof}  Michael Keller committed May 11, 2022 170 171 172 173 174 175 176 177 178 179  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 relational to field size and number of crop types. Finally we test if the score $S(F', R)$ is at least $s$.  Michael Keller committed May 11, 2022 180 181 182  For the proof of NP Hardness we again reduce to the hamiltonian paths problem as in the proof that  Michael Keller committed May 11, 2022 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198  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:  Michael Keller committed May 11, 2022 199 200 201 202 203 204 205 206 207 208  \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} \end{proof}  Michael Keller committed May 13, 2022 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  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.  Michael Keller committed May 11, 2022 238   Michael Keller committed May 13, 2022 239  TODO: MAKE MORE FORMAL  Michael Keller committed May 11, 2022 240   Michael Keller committed May 13, 2022 241 242 243 244  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.  Michael Keller committed Apr 20, 2022 245 \end{proof}