hardness.tex 7.27 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 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  \section{Fractional Pixel Farming is NP Complete} We consider a slightly modified version of the pixel farming decision problem. Instead of allowing a pixel to only contain a single crop, a pixel may now contain multiple crops. We do however still require that the total amount of crops planted within a pixel sums to one. 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. \begin{theorem} The fractional pixel farming problem (decision version) is NP complete. \end{theorem} \begin{proof} We want to show that the question: Does there exist a fractional solution to the pixel farming problem such that the score $S(F, R)$ for a field $F$ and relationship function $R$ is at least $s$?'' is NP complete. The problem is obviously in NP, as we can calculate the score of a given field $F$ and relationship function $R$ in polynomial time. 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. We show that the following implications hold for any graph $G$: \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} The first implication is trivial. The second implication we prove indirectly. We show instead that the following statement holds: There exists no Hamiltonian path in $G$'' $\implies$ No optimal fractional solution to the constructed pixel farming problem exists.''  Michael Keller committed Apr 20, 2022 196 \end{proof}