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

Michael Keller's avatar
Michael Keller committed
3
We prove that the problem of finding a
4
5
solution of a certain quality to a pixel
farming problem is NP complete.
Michael Keller's avatar
Michael Keller committed
6
7
8
9
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
Michael Keller's avatar
Michael Keller committed
10
Hamiltonian Paths, which will imply that finding
Michael Keller's avatar
Michael Keller committed
11
solutions for pixel farming is NP complete.
Michael Keller's avatar
Michael Keller committed
12
13
14

\section{The decision version of pixel farming}

Michael Keller's avatar
Michael Keller committed
15
16
We define the decision version of the pixel farming
problem very similarly to the
Michael Keller's avatar
Michael Keller committed
17
18
regular version. However, instead of asking
for a field with the maximum score, we ask
Michael Keller's avatar
Michael Keller committed
19
for a field with a score of at least $s$. Formally:
Michael Keller's avatar
Michael Keller committed
20
21
22
23
24
25
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's avatar
Michael Keller committed
26
\section{Pixel Farming is NP Complete}
27
28
29
30
31
32
33
34
35
36

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

Michael Keller's avatar
Michael Keller committed
38
First, we non-deterministically select
Michael Keller's avatar
Michael Keller committed
39
40
a field $F$ for a given relation
function $R$. By computing the score $S(F, R)$, which
Michael Keller's avatar
Michael Keller committed
41
42
can be done in polynomial time in relation to the field
size $X \cdot Y$, we can easily test wether the score
Michael Keller's avatar
Michael Keller committed
43
44
45
46
47
48
49
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$.

50

Michael Keller's avatar
Michael Keller committed
51
It is known that finding Hamiltonian Paths is NP
Michael Keller's avatar
Michael Keller committed
52
53
complete \cite[Page 199, GT39]{alma990005774300205503}.
Thus, reducing the decision version
Michael Keller's avatar
Michael Keller committed
54
of Hamiltonian Paths (explained below) to the decision
Michael Keller's avatar
Michael Keller committed
55
56
57
58
59
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
Michael Keller's avatar
Michael Keller committed
60
61
62
decision version of the Hamiltonian Path problem as follows:
Does a path that visits every vertex
in the graph exactly once exist?
Michael Keller's avatar
Michael Keller committed
63

Michael Keller's avatar
Michael Keller committed
64
65
\paragraph{Reduction} We assume we are given an undirected
graph $G$ and a polynomial time algorithm in $X \cdot Y$
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
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's avatar
Michael Keller committed
72
73
decision problem on a $1 \times \abs{V}$ field
with a score that means every pixel
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
86
\FloatBarrier
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
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's avatar
Michael Keller committed
121
If we get the answer that no solution
Michael Keller's avatar
Michael Keller committed
122
123
124
with value at least $s$ exists, we conclude that no longest path of
length $\abs{V} - 1$ exists. If, on the other hand, a solution
of at least $s$ exists, we know that a hamiltonian path
Michael Keller's avatar
Michael Keller committed
125
126
must exist in $G$.

Michael Keller's avatar
Michael Keller committed
127
The rationale for this is as follows: Let us assume
Michael Keller's avatar
Michael Keller committed
128
129
130
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's avatar
Michael Keller committed
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's avatar
Michael Keller committed
133
134
135
136
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$.

Michael Keller's avatar
Michael Keller committed
137
If, on the other hand, no arrangement of value at least $s$
Michael Keller's avatar
Michael Keller committed
138
139
140
141
142
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.
143

Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
146
147
\end{proof}

Michael Keller's avatar
Michael Keller committed
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
196
197
198
199
200
201
202
203
204
205
206
207
208
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
238
239
240
241
242
243
244
245
% \section{Fractional Pixel Farming is NP Complete}
% We consider the slightly modified version of the
% standard pixel farming decision problem. Instead of allowing
% a pixel to only contain a single crop,
% a pixel may now contain multiple crops, as explained
% in the problem definition section. 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.

% We define the decision version of fractional pixel farming
% analogously to the standard version: Does a field $F'$
% 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*}

% \begin{theorem}
%     The fractional pixel farming problem (decision version) is NP complete.
% \end{theorem}

% \begin{proof}
%     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 relative to field size and number
%     of crop types. Finally, we test if the score $S(F', R)$
%     is at least $s$.

%     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. 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:
%     \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}
%
%     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.

%     TODO: MAKE MORE FORMAL

%     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.
% \end{proof}