One of the first and well known problems in finite model theory, called Asser's conjecture,
asks whether the complement of a spectrum is also a spectrum [1]}.
It turns out to be equivalent to \(\textsc {NE}\)  vs. \(\textsc {co-NE}\) 
problem [2]}, [3]}, [4]}.\(\textsc {NE}\)  is the class of languages accepted
by a non-deterministic (possibly multi-tape) Turing machine with run time
\(O(2^{kn})\) , for some constant \(k > 0\) .
More specifically, it is shown that the class \(\textsc {NE}\)  is captured precisely by \(\textsc {Spec}\) 
in the following sense:
For every spectrum \(A\) , the language that consists of the binary representations of the numbers in \(A\) 
belongs to the class \(\textsc {NE}\) , and vice versa,
for every language \(L \subseteq 1\cdot \lbrace 0,1\rbrace ^*\)  , i.e., it consists of only words that start with symbol 1,
if \(L \in \textsc {NE}\) , then the set of integers whose binary representations are in \(L\)  is a spectrum.
For a more comprehensive treatment on the spectrum problem
and its history,
we refer interested readers to an excellent survey by
Durand, Jones, Makowsky and More [5]}, and the references therein.
