hardness.tex 5.03 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 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 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 perfect solutions for pixel farming is NP complete. \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 38 39 40 41 42 43 44 45 46 47 48  Assume we are given a field $F$ and a relation function $R$. By computing $S(F, R)$, which 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 49   Michael Keller committed Apr 19, 2022 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 It is known that finding Hamiltonian Paths is NP complete. Thus, reducing the decision version 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: Does there exists a path in $G$ of length at least $l$ where every vertex in the path is visited only once? \paragraph{Reduction} We assume we are given a graph $G$, a length $l$ and a polynomial time algorithm in $X \cdot Y$ 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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 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 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 Let us first look at a simple case, when $l = \abs{V}$. The core idea is that we translate vertices to crops and edges to crops liking each other. Then, a pixel farming decision problem with a score that means every pixel 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: \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 What about the case where $l < \abs{V}$? For this we need to resort to a trick. Say for example we are looking for a path of length at least $\abs{V} - 2$. We can't simply change $s$ to be $4$ less than before, because we have no guarantees as to where these cuts'' will be. We could end up in a situation where our pixel farming algorithm gives us 3 paths that are all not of sufficient length. \begin{figure}[h] \centering \begin{tikzpicture}[node distance={0.5cm}, main/.style = {draw, minimum size=0.5cm}] \node[main] (1) {}; \node[main] (13) [below of =1] {}; \foreach \x in {2,...,12} { \pgfmathtruncatemacro{\prev}{\x - 1} \pgfmathtruncatemacro{\below}{\x + 11} \node[main] (\x) [right of=\prev] {}; \node[main] (\below) [below of=\x] {}; } \node[main] (26) [below of=20] {}; \node[main] (27) [below of=22] {}; \end{tikzpicture} \hfill \caption{example structure} \end{figure}  Michael Keller committed Apr 20, 2022 139 140 141 \FloatBarrier \end{proof}