NpHardProblemsTopology.tex

\section{NP-hard problems in topology}

In this last section we finally want to bring everything together. We will apply the existence of algebraic
models for spaces and the $\NPcomplexity$-hardness of certain of their properties to problems in topology.
We shall use space to mean topological space and all maps are meant to be continous.

\subsection{Some definitions of topological invariants}
\label{sec:DefinitionsOfTopologicalInvariants}

\begin{Definition}
 Let $I^n \coloneqq [0,1]^n$ be the $n$-dimensional unit cube and $\partial I^n$ its boundary.
 For $n \geq 0$ the \emph{homotopy groups} of a space $X$ with basepoint $x_0 \in X$ are defined as follows: 
 $$\pi_n(X) \coloneqq [(I^n, \partial I^n), (X,x_0) ]$$
 is the set of homotopy classes of maps
 $f \colon I^n \to X$ with $f(\partial I^n) = x_0$ where homotopies $h_t$ have to satisfy $h_t(\partial I^n) = x_0$.
 Furthermore, we define the group multiplication by 
 $$ (f \cdot g) (x_1, \ldots, x_n) \coloneqq 
 \begin{cases}
  f(2x_1, x_2, \ldots, x_n) &\text{for $x_1 \in [0, \frac{1}{2}]$} \\
 
  g(2x_1 - 1, x_2, \ldots, x_n) &\text{for $x_1 \in [ \frac{1}{2}, 1]$}
 \end{cases}
$$
A map $f \colon X \to Y$ induces a homomorphism $\pi_n(f) \colon \pi_n(X) \to \pi_n(Y)$
on homotopy groups by 
$(\pi_n(f)) ([\varphi]) \coloneqq [f \circ \varphi]$.
\end{Definition}

Note that collapsing the boundary of $I^n$ yields $S^n$ and we could have defined 
$\pi_n(X) \coloneqq [ (S^n, y_0), (X,x_0)]$ where $y_0$ represents $[\partial I^n]$.

\begin{Remark}
 A connected space $X$ with $\pi_1(X) = 0$ is called \emph{simply connected}. We shall only consider
 simply connected spaces since it can be shown that $\pi_n (X)$ is abelian for $n \geq 2$ 
 (\cite{SWB-334616069} p.\ 340)
 which allows us to consider the \emph{rational homotopy groups}
 $ \pi_n(X) \otimes_{\Z} \Q$ (for $n \geq 2$) of $X$. Rational homotopy groups become interesting since the ``normal''
 homotopy groups of many spaces are virtually not computable by any known method whereas rational homotopy groups
 are easy to compute for many spaces.
\end{Remark}

In the next theorem we shall see how rational homotopy groups of a space are connected with 
the Sullivan model of the space.

\begin{Theorem}
\label{thm:MainTheoremOfRationalHomotopyTheory}
 Let $X$ be a simply connected space with $H^i(X)$ finite dimensional for all $i \geq 0$ and 
 $(\Lambda V_X, d)$ a minimal Sullivan model of $X$ then
 
 $$ \pi_*(X) \otimes \Q \cong V_X.$$
\end{Theorem}

\begin{proof}
 From~\cite{Felix2001} Theorem 15.11 we cite the essential part of the proof, namely $V_X \cong Hom_{\Z}(\pi_*(X), \Q)$. 
 From this we get 
 $$ V_X \cong Hom_{\Z}(\pi_*(X), \Q) \cong Hom_{\Z}(\pi_*(X), Hom_{\Z}(\Q, \Q)) \cong 
  Hom_{\Z}(\pi_*(X) \otimes \Q, \Q) \cong \pi_*(X) \otimes \Q$$
  
  where we have used that $Hom$ and tensor product are adjoint.
\end{proof}

This theorem yields a powerful tool for computing rational homotopy groups.
\begin{Example}
\label{ex:RationalHomotopyGroupsOfSpheres}
 We know from~\ref{ex:MinimalModelOfSpheresAPL} that $\Lambda(v_{2k+1};)$ and $\Lambda(v_{2k}, x_{4k -1}; dx = v^2)$
 define  minimal Sullivan models of the odd and even dimensional spheres. Therefore, we now also know their rational homotopy groups:
 
 \begin{multicols}{2}
  $\pi_i(S^{2k+1}) \otimes \Q \cong
  \begin{cases}
  \Q  	&\text{for $i = 0, 2k+1$} \\
  0 	&\text{else}
  \end{cases}
  $
  
  \columnbreak
  
  $\pi_i(S^{2k}) \otimes \Q \cong
  \begin{cases}
  \Q  	&\text{for $i = 0, 2k, 4k -1 $} \\
  0 	&\text{else}
  \end{cases}
  $
 \end{multicols}
This implies in particular that all homotopy groups of the $n$-sphere are torsion besides in degrees $0, n$
and for $n$ even $2n -1$.
\end{Example}

In the next section we will to prove statements about the complexity of certain problems for topological spaces.
For this, we have to represent topological spaces in a computer. Unfortunately, we can not represent topological
spaces by storing them as sets with a topology. For this reason, we now illustrate certain characteristics of
topological spaces which characterise the homotopy type of the space and can
be represented (in form of a Sullivan model or something similar) in a computer.

\begin{Definition}
 A \emph{weak homotopy equivalence} between two spaces $X$ and $Y$ is a map $f \colon X \to Y$ for which
 $\pi_n(f)$ is an isomorphism for all $n$. Two spaces $X$ and $Y$ have the same \emph{weak homotopy type}
 if there is a finite chain of weak homotopy equivalences connecting them, i.e.\ there is
 $$ X \leftarrow Z_1 \rightarrow \ldots \leftarrow Z_n \rightarrow Y $$
 where all the maps are weak homotopy equivalences.
\end{Definition}

\begin{Remark}
 It is reasonable to speak of weak homotopy equivalences since the Theorem of Whitehead (\cite{SWB-334616069} Theorem 4.5)
 states that a weak homotopy equivalence of CW complexes always is a homotopy equivalence.
\end{Remark}


\begin{Definition}
 A \emph{rational space} is a simply connected space $X$ with $\pi_*(X)$ being a $\Q$-vector space.
 Additionally, a  \emph{rationalisation} of a space $X$ is a rational space $X_{\Q}$ together with a map
 $f \colon X \to X_{\Q}$ such that $\pi_*(f) \otimes_{\Z} id_{\Q}$ is an isomorphism. 
 A map $\varphi \colon X \to Y$ for which $\pi_*(\varphi) \otimes \Q$ is an isomorphism is 
 called a \emph{rational homotopy equivalence} and rational homotopy equivalent spaces will be denoted by
 $X \simeq_{\Q} Y$.
\end{Definition}

\begin{Remark}
 For every simply connected space $X$ a rationalisation $X_\Q$ of $X$ exists (\cite{Felix2001} Theorem 9.7).
 This allows us to define the \emph{rational homotopy type} of a simply connected space $X$ as the weak homotopy type of $X_\Q$.
 From this definition we get that two simply connected
 spaces $X$ and $Y$ have the same rational homotopy type if and only if there is a finite chain
 of rational homotopy equivalences
 $$ X \overset{\simeq_\Q}{\leftarrow} Z_1 \overset{\simeq_\Q}{\rightarrow} \ldots \overset{\simeq_\Q}{\leftarrow}
 Z_n \overset{\simeq_\Q}{\rightarrow} Y.$$
 Further, it can be shown that a map $f \colon X \to Y$ between simply connected spaces $X$ and $Y$
 is a rational homotopy equivalence if and only if $H^*(f;\Q)$ 
 is an isomorphism (\cite{Felix2001} Theorem 8.6). Therefore, for two simply connected
 spaces $X$ and $Y$ which have the 
 same rational homotopy type the algebras $A_{PL}(X)$ and $A_{PL}(Y)$ are weakly equivalent and hence they 
 have (up to isomorphism) the same minimal Sullivan model. The converse is also true, i.e.\ if two
 spaces have the same minimal Sullivan model then they have the same rational homotopy type (\cite{Felix2001} Chapter 17).
 Hence, we can encode the rational homotopy type of a simply connected space by encoding its Sullivan algebra.
\end{Remark}


For our purposes, an important form of rationalisation is the spatial realisation.

\begin{Theorem}
 If $\Sullivan$ is a simply connected Sullivan algebra with $H^i \Sullivan$ finite dimensional for all $i$ then
 $| \langle \Sullivan \rangle |$ is a rational space. Further, if $X$ is a simply connected CW complex with 
 $H^i(X)$ finite dimensional for all $i$ and $\Sullivan$ is a minimal Sullivan model of $X$ then there is 
 a map $h_X \colon X \to | \langle \Sullivan \rangle |$ which is a rationalisation.
\end{Theorem}

\begin{proof}
 See~\cite{Felix2001} Theorem 17.10 and 17.12.
\end{proof}


This allows us to explicitly construct a rationalisation of the class of spaces we are interested in.
In the following we shall introduce some topological invariants which only depend on the rational homotopy type of a
space. They shall be connected with the properties we earlier introduced for Sullivan algebras and we shall
show that their computation is $\NPcomplexity$-hard.
\begin{Definition}
 The \emph{Lusternik-Schnirrelman category} $cat(X)$ of a space $X$ is the smallest integer $k$ such that 
 $X$ can be covered by open sets $U_1, \ldots, U_{k+1}$ that are all contractible in $X$ which
 means that the inclusions $U_i \xhookrightarrow{} X$ are homotopic to a constant map.
 The \emph{rational Lusternik-Schnirrelman category} $cat_0(X)$ of $X$ is the smallest integer $k$ such that there is a space $Y$
 with $ X \simeq_{\Q} Y$ and $cat \, Y = k$.
\end{Definition}

\begin{Remark}
 It is important that the sets $U_i$ are contractible in X. 
 An example of the difference to the term contractible is $S^n$ which is not contractible but contractible in $\R^{n+1}$. 
\end{Remark}

\begin{Example}
 The Lusternik-Schnirrelman category of a contractible space is zero and the converse also holds.
 A sphere $S^n$ is not contractible but can be covered by extended upper and lower hemispheres which
 overlap a  bit at the equator. Therefore, $S^n$ has Lusternik-Schnirrelman category one.
\end{Example}

The reader probably noticed that we already defined Lusternik-Schnirrelman category for Sullivan algebras and
of course these two notions coincide in nice cases:

\begin{Proposition}
 Let $X$ be a simply connected space with $H^i(X)$ finite dimensional for $i \geq 0$ and let $\Sullivan$ be 
 a Sullivan model of $X$ then
 $$ cat \, \Sullivan = cat_0 (X)$$
\end{Proposition}

\begin{proof}
 See~\cite{Felix2001} Proposition 29.4.
\end{proof}

\begin{Definition}
 We call $b_p (X) \coloneqq dim \, H^p(X)$ the \emph{Betti numbers} of a space $X$.
\end{Definition}

\begin{Example}
 The Betti numbers of $S^n$ are $b_0(S^n) = b_n(S^n) = 1$ and $ b_i(S^n) = 0$ else.
\end{Example}

For us, the Betti numbers serve as a numerical invariant of a space which is easier to compute than computing the whole cohomology
of the space. We shall show that their computation is still $\NPcomplexity$-hard. Moreover, the Betti numbers
of a minimal Sullivan model of a space coincide with the Betti numbers of the space. This is clear since taking 
homology of the minimal Sullivan model yields the cohomology of the space.

\begin{Definition}
 A simply connected space $X$ is called \emph{rationally elliptic} if both $H^*(X)$ and $\pi_*(X) \otimes \Q$ are finite dimensional.
\end{Definition}

\begin{Example}[Again the spheres]
 The spheres (our preferred example) $S^n$ for $n \geq 2$ are elliptic by Example~\ref{ex:RationalHomotopyGroupsOfSpheres}.
\end{Example}

Further, the machinery developed in Section~\ref{sec:FromSpacesToAlgebras} easily allows us to construct non-elliptic spaces 
as follows:
 \begin{Example}
  In this example, we shall construct a space with infinite dimensional rational homotopy groups but no cohomology.
  For this, consider the Sullivan algebra $\Sullivan$
  ${V \coloneqq \bigoplus_{i \in \N} \langle x_i \rangle \oplus \bigoplus_{j \in \N} \langle y_j \rangle}$ with
  $|x_i| = 2i$, $|y_i| = 2i + 1$ and define the differential by $dx_i = y_i$ and $dy_i = 0$. This Sullivan algebra
  has no homology hence its spatial realisation $ X \coloneqq | \langle \Sullivan \rangle |$ has no cohomology and
  by Theorem~\ref{thm:MainTheoremOfRationalHomotopyTheory} it has infinite dimensional rational homotopy groups.
 \end{Example}
 
 \begin{Example}
  In the spirit of the last example we can also construct a space with infinite dimensional cohomology and 
  finite dimensional rational homotopy groups. For this, consider the Sullivan algebra 
  $\Sullivan \coloneqq \Lambda(a_2 ;)$. Its spatial realisation $ X \coloneqq | \langle \Sullivan \rangle |$ has the cohomology
  algebra $H^*(X) \cong \Q[a]$ (with $|a| = 2$) and by Theorem~\ref{thm:MainTheoremOfRationalHomotopyTheory} only
  $\pi_2(X) \cong \Q$ is not isomorphic to zero.
 \end{Example}



\begin{Remark}
 From Theorem~\ref{thm:MainTheoremOfRationalHomotopyTheory} we can see that a minimal model $(\Lambda V_X,d)$ of a
 rationally elliptic space $X$ is always an elliptic Sullivan algebra.
\end{Remark}


%TODO mehr Erklärungen

\begin{Definition}
 The \emph{rational cup length} $c_0 (X)$ of a space $X$ is the product length of its rational cohomology algebra,
 i.e. 
 $$ c_0 (X) \coloneqq nil \, H^*(X) $$
\end{Definition}



\subsection{$\NPcomplexity$-hard problems in rational homotopy theory}

In this last section we want to translate Section~\ref{sec:NPSullivan} to topology.

%TODO Besser formulieren!, wir kodieren nur rationalen homotopie typ
\begin{Remark}
 In order to speak about the complexity of computations involving topological spaces we first have to
 fix an encoding of topological spaces in a computer. We therefore restrict ourselves to encoding the
 rational homotopy type of simply connected
 spaces $X$ with $\pi_*(X) \otimes \Q$ finite dimensional and $H^i(X)$ finite dimensional for all $i \in N$
 (note that this not necessarily requires that $X$ is elliptic). If $X$ is such a space then
 its minimal model $(\Lambda V_X, d)$ has finite dimensional $V_X$ and thus
 we can encode the rational homotopy type of $X$ by encoding its Sullivan model using the encoding from 
~\ref{rem:CodingOfSullivanAlgebras}. 
\end{Remark}

\begin{Theorem}[Lechuga, Murillo]
\label{thm:SpacesDecidingEllipticity}
 It is a $\NPcomplexity$-hard problem to decide if a given simply connected space $X$ with  $\pi_*(X) \otimes \Q$
 finite dimensional is elliptic.
\end{Theorem}

\begin{proof}
 This follows directly from~\ref{thm:DecidingEllipticityIsNpHard} as follows:
 Given a  Sullivan algebra $\Sullivan$ with $V = { \{ V^n \} }_{n \geq 2}$ finite dimensional we construct the 
 space $| \langle \Sullivan \rangle |$ which is simply connected and 
 $\pi_*(| \langle \Sullivan \rangle |) \otimes \Q$ is finite dimensional. Further, we know that 
 $H^*(| \langle \Sullivan \rangle |) \cong H \Sullivan$ and therefore the decision problem for 
 spaces is at least as hard as for Sullivan algebras.
\end{proof}

\begin{Remark}
 In fact, we can restrict this result to a smaller class of spaces. If we consider $k = 3$ the spaces resulting from
 the Sullivan algebras $\Sullivan$ constructed in~\ref{constructionOfSullivanAlgebra} only have nonvanishing rational
 homotopy groups in degree 2 and 3. Consequently, deciding if a simply connected space $X$ with
 $\pi_i(X) \otimes \Q = 0$ for $i \neq 0,2,3$ is elliptic is still $\NPcomplexity$-hard and this is a stronger result than
~\ref{thm:SpacesDecidingEllipticity}.
\end{Remark}

\begin{Theorem}[Garvín, Lechuga]
 Computing the Betti numbers of an elliptic space is $\NPcomplexity$-hard.
\end{Theorem}

\begin{proof}
 Computing the Betti numbers of a given elliptic Sullivan algebra $\Sullivan$ is the same as computing
 them for $ | \langle \Sullivan \rangle |$, so the problem is $\NPcomplexity$-hard by~\ref{thm:AlgebrasComputingBettiNumbers}.
\end{proof}


In the end we have a look at spaces where the rational homotopy type is already encoded in the cohomology 
algebra of the space.

\begin{Definition}
 A space $X$ is called \emph{formal} if there is a quasi-isomorphism
 $$ \varphi \colon (\Lambda V_X , d) \to (H^*(X),0)$$
 where $(\Lambda V_X,d)$ is a minimal model of $X$.
\end{Definition}

\begin{Example}
 The spheres $S^n$ for $n \geq 2$ are formal as we have seen in~\ref{ex:MinimalModelOfSpheresAPL}. 
\end{Example}

\begin{Example}
With the same computation as for spheres, one shows that $\C P^n$, $\Quaternions P^n$,
$\C P^{\infty}$ and $\Quaternions P^{\infty}$ are formal.
\end{Example}


\begin{Remark}
 If we know the cohomology algebra $H^*(X)$ of a simply connected and formal space $X$, we can compute a minimal Sullivan model
 $\Sullivan$ of $H^*(X)$ which also is a minimal Sullivan model of $A_{PL}(X)$ since 
 minimal Sullivan models are unique up to isomorphism by~\ref{thm:UniquenessOfModels}. Thus, we can say
 that the rational homotopy type of $X$ (encoded in $(\Lambda V_X,d))$ is a ``formal consequence'' of its 
 cohomology algebra.
\end{Remark}

\begin{Remark}
\label{rem:EncodingOfFormalSpaces}
 The last remark allows us to have an own computer representation of the rational homotopy type of 
 a formal space $X$ since we only have to store its cohomology algebra. Therefore, we represent a 
 formal space with finitely generated cohomology algebra as follows. 
 Take the cohomology algebra of $X$ and write it as $H^*(X) \cong \Lambda V / I$ where $V$ is a vector
 space and $I$ is an ideal. Then, encode $X$ as the generators $v_1, \ldots, v_n$ of $V$ and the generators 
 of $I$ of the form $\sum_{i_1 \ldots i_n} \lambda_{i_1, \ldots , i_n} v_1^{i_1} \cdots v_n^{i_n}$.
\end{Remark}


This allows us to formulate another $\NPcomplexity$-hard problem:

%TODO finite complex?
\begin{Theorem}
\label{thm:RationalCupLengthOfFormalSpacesIsNPHard}
 Computing the rational cup length $c_0 (X)$ of a formal space $X$ is $\NPcomplexity$-hard.
\end{Theorem}


\begin{proof}
 We  prove the theorem by reducing  INDSET to the problem of computing rational cup lenghts of formal spaces. 
 
 Given an instance of INDSET, that is, a graph $G = (V,E)$ with $V = \lbrace v_1 , \ldots , v_n \rbrace$ and 
 $E = \lbrace \, \lbrace v_i, v_j \rbrace \; | \; (i,j) \in S \rbrace$, we construct an algebra 
 $A \coloneqq \Lambda V /I$ where $V \coloneqq \langle x_1, \ldots , x_n \rangle$ with $|x_i| = 3$ and I generated by
 the elements $x_i x_j$ for $(i,j) \in S$. Now let $(\Lambda W,d)$ be a minimal Sullivan model of $(A,0)$. In particular,
 $A$ is  the cohomology algebra of the formal space $ | \langle (\Lambda W,d) \rangle | $. 
 We can encode $| \langle (\Lambda W,d) \rangle |$ by encoding $A$ as defined in~\ref{rem:EncodingOfFormalSpaces}.
 
 Constructing $A$ from $G$ takes linear time in the size of $G$.
 This is because the number of generators of $V$ equals the number of vertices in $G$, 
 and the number of generators of $I$ equals the number of edges of $G$. 
 
 To finish the proof, we show that the product length of $A$--and hence the rational cup length of 
 $| \langle (\Lambda W,d) \rangle | $)--equals the size of the largest
 independent set in $G$. This can be seen as follows.
 Let $(v_k)_{k \in K}$ be the largest independent set in $G$. We have by definition for $i,j \in K$ with  $i\neq j$
 that $x_i x_j \notin I$ and therefore $\Pi_{k \in K} x_k \neq 0$. Hence, $nil \, A \geq |K|$. On the other hand,
 if $nil \, A = m$ and we have a product  $\Pi_{i = 1}^m x_{i_m} \neq 0$, we obtain by the definition of $I$ that 
 $(v_{i_m})_{i = 1, \ldots, m}$ is an independent set of size $m$. 
 
 In summary, we have shown that if we can compute
 the rational cup length of a formal space $X$, we can compute, with polynomial overhead, the size of the largest
 independent set of a given graph.
 
\end{proof}

\begin{Remark}
 The new encoding for formal spaces from Remark~\ref{rem:EncodingOfFormalSpaces} is necessary for the proof given 
 for Theorem~\ref{thm:RationalCupLengthOfFormalSpacesIsNPHard}. This is because the algebra $\Lambda V /I$ constructed
 in the proof does not have a Sullivan model $(\Lambda W, d)$ with finite dimensional $W$. One can see
 this by applying Algorithm~\ref{alg:ConstructionOfMinimalSullivanAlgebra} to $\Lambda V /I$.
 Hence, $ | \langle (\Lambda W,d) \rangle | $ could not be represented by the old encoding, which uses Sullivan models,
 so the proof would fail.
\end{Remark}