hardness.tex 5.03 KB
Newer Older
Michael Keller's avatar
Michael Keller committed
1
2
\chapter{Computational Hardness}

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's avatar
Michael Keller committed
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}

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's avatar
Michael Keller committed
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$.

49

Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
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}
139
140
141
\FloatBarrier

\end{proof}