  In neuroscience, an important aspect of understanding the function of a
neural circuit is to determine which, if any, of the neurons in the circuit are
vital for the biological behavior governed by the neural circuit. A similar
problem is to determine whether a given small set of neurons may be enough for
the behavior to be displayed, even if all other neurons in the circuit are
deactivated. Such a subset of neurons forms what is called a degenerate circuit
for the behavior being studied.
  Recent advances in experimental techniques have provided researchers with
tools to activate and deactivate subsets of neurons with a very high
resolution, even in living animals. The data collected from such experiments
may be of the following form: when a given subset of neurons is deactivated, is
the behavior under study observed? This setting leads to the algorithmic
question of determining the minimal vital or degenerate sets of neurons when
one is given as input a description of the neural circuit. The algorithmic
problem entails both figuring out which subsets of neurons should be perturbed
(activated/deactivated), and then using the data from those perturbations to
determine the minimal vital or degenerate sets. Given the large number of
possible perturbations, and the recurrent nature of neural circuits, the
possibility of a combinatorial explosion in such an approach has been
recognized in the biology and the neuroscience literature.
  In this paper, we prove that the problems of finding minimal or minimum-size
degenerate sets, and of finding the set of vital neurons, of a neural circuit
given as input, are in fact PSPACE-hard. More importantly, we prove our
hardness results by showing that a simpler problem, that of simulating such
neural circuits, is itself PSPACE-hard.
