Up: Supplementary Text Topics
In 1952 Scholz asked about the possibilities for the set of sizes of the finite models of a first-order sentence.
Let us look at some examples of spectra.
An interesting set of models is obtained by using a modification of Dedekind's approach to the natural numbers, namely let our language be and let be the conjunction of the statements:
One can easily show that the union or intersection of two spectra is again a spectrum (make the languages of
disjoint and consider
In 1956 Asser looked at the question of whether the complement of a spectrum is again a spectrum -- the problem is still open.
A fascinating result was proved by Jones and Selman in 1974 when they showed that a subset of N is a spectrum iff it can be accepted by some nondeterministic Turing machine in time
. From this it follows that if NP is closed under complements, i.e., NP = co-NP, then spectra are also closed
under complements. Consequently to show that spectra are not closed under complements is at least as difficult as showing NP
co-NP, and hence P
Up: Supplementary Text TopicsStan Burris