hardness.tex 2.33 KB
 Michael Keller committed Apr 19, 2022 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 \chapter{Computational Hardness} We show that the problem of finding a perfect solution to a pixel farming problem is NP complete. 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} \section{Pixel Farming is in NP} 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$. \section{Pixel Farming finds Hamiltonian Paths} 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$. In polynomial time we build the following pixel farming decision problem. Our crops are as follows: \begin{displaymath} \Cps = V \cup \{ \abs{V} + 1, \dots, \abs{V} + 1 + l + \} \end{displaymath}