  In this paper, we discuss the computational complexity of reconstructing the
state of a linear system from sensor measurements that have been corrupted by
an adversary. The first result establishes that the problem is, in general,
NP-hard. We then introduce the notion of eigenvalue observability and show that
the state can be reconstructed in polynomial time when each eigenvalue is
observable by at least $2s+1$ sensors and at most $s$ sensors are corrupted by
an adversary. However, there is a gap between eigenvalue observability and the
possibility of reconstructing the state despite attacks - this gap has been
characterized in the literature by the notion of sparse observability. To
better understand this, we show that when the $\mathbf{A}$ matrix of the linear
system has unitary geometric multiplicity, the gap disappears, i.e., eigenvalue
observability coincides with sparse observability, and there exists a
polynomial time algorithm to reconstruct the state provided the state can be
reconstructed.
