hardness.tex 9.36 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
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's avatar
Michael Keller committed
11
solutions for pixel farming is NP complete.
Michael Keller's avatar
Michael Keller committed
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}

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

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

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
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's avatar
Michael Keller committed
61
62
Does there exist a path that visits every vertex
in the graph exactly once?
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
with value at least $s$ exists, we return that no longest path of
Michael Keller's avatar
Michael Keller committed
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'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
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.
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

\section{Fractional Pixel Farming is NP Complete}
Michael Keller's avatar
Michael Keller committed
148
149
We consider the slightly modified version of the
standard pixel farming decision problem. Instead of allowing
Michael Keller's avatar
Michael Keller committed
150
a pixel to only contain a single crop,
Michael Keller's avatar
Michael Keller committed
151
152
a pixel may now contain multiple crops, as explained
in the problem definition section. One might suspect that
Michael Keller's avatar
Michael Keller committed
153
154
155
156
such a relaxation might enable us to formulate a
convex optimization problem. We show however that
this relaxation is also NP complete.

Michael Keller's avatar
Michael Keller committed
157
We define the decision version of fractional pixel farming
Michael Keller's avatar
Michael Keller committed
158
analogously to the standard version: Does a field $F'$
Michael Keller's avatar
Michael Keller committed
159
160
161
162
163
164
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*}

Michael Keller's avatar
Michael Keller committed
165
166
167
168
169
\begin{theorem}
    The fractional pixel farming problem (decision version) is NP complete.
\end{theorem}

\begin{proof}
Michael Keller's avatar
Michael Keller committed
170
171
172
173
174
175
176
177
178
179
    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 relational to field size and number
    of crop types. Finally we test if the score $S(F', R)$
    is at least $s$.
Michael Keller's avatar
Michael Keller committed
180
181
182

    For the proof of NP Hardness we again reduce to the
    hamiltonian paths problem as in the proof that
Michael Keller's avatar
Michael Keller committed
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
    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:
Michael Keller's avatar
Michael Keller committed
199
200
201
202
203
204
205
206
207
208
    \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}

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

Michael Keller's avatar
Michael Keller committed
239
    TODO: MAKE MORE FORMAL
Michael Keller's avatar
Michael Keller committed
240

Michael Keller's avatar
Michael Keller committed
241
242
243
244
    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.
245
\end{proof}