  We study linear equations in combinatorial Laplacians of $k$-dimensional
simplicial complexes ($k$-complexes), a natural generalization of graph
Laplacians. Combinatorial Laplacians play a crucial role in homology and are a
central tool in topology. Beyond this, they have various applications in data
analysis and physical modeling problems. It is known that nearly-linear time
solvers exist for graph Laplacians. However, nearly-linear time solvers for
combinatorial Laplacians are only known for restricted classes of complexes.
  This paper shows that linear equations in combinatorial Laplacians of
2-complexes are as hard to solve as general linear equations. More precisely,
for any constant $c \geq 1$, if we can solve linear equations in combinatorial
Laplacians of 2-complexes up to high accuracy in time $\tilde{O}((\# \text{ of
nonzero coefficients})^c)$, then we can solve general linear equations with
polynomially bounded integer coefficients and condition numbers up to high
accuracy in time $\tilde{O}((\# \text{ of nonzero coefficients})^c)$. We prove
this by a nearly-linear time reduction from general linear equations to
combinatorial Laplacians of 2-complexes. Our reduction preserves the sparsity
of the problem instances up to poly-logarithmic factors.
