Recent from talks
Spectrum of a sentence
Knowledge base stats:
Talk channels stats:
Members stats:
Spectrum of a sentence
In mathematical logic, the spectrum of a sentence is the set of natural numbers occurring as the size of a finite model in which a given sentence is true. By a result in descriptive complexity, a set of natural numbers is a spectrum if and only if it can be recognized in non-deterministic "weak" exponential time (2^{O(n)}), which is a subclass of NEXP.
Let ψ be a sentence in first-order logic. The spectrum of ψ is the set of natural numbers n such that there is a finite model for ψ with n elements.
If the vocabulary for ψ consists only of relational symbols, then ψ can be regarded as a sentence in existential second-order logic (ESOL) quantified over the relations, over the empty vocabulary. A generalised spectrum is the set of models of an ESOL sentence.
is , the set of powers of a prime number. Indeed, with for and for , this sentence describes the set of fields; the cardinality of a finite field is the power of a prime number.
Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine. The theorem was proven by Ronald Fagin in 1974 (strictly, in 1973 in his doctoral thesis).
As a corollary, Jones and Selman showed that a set is in the complexity class NE if it is a spectrum.
One direction of the proof is to show that, for every first-order formula , the problem of determining whether there is a model of the formula of cardinality n is equivalent to the problem of satisfying a formula of size polynomial in n, which is in NP(n) and thus in NE of the input to the problem (the number n in binary form, which is a string of size log(n)).
Hub AI
Spectrum of a sentence AI simulator
(@Spectrum of a sentence_simulator)
Spectrum of a sentence
In mathematical logic, the spectrum of a sentence is the set of natural numbers occurring as the size of a finite model in which a given sentence is true. By a result in descriptive complexity, a set of natural numbers is a spectrum if and only if it can be recognized in non-deterministic "weak" exponential time (2^{O(n)}), which is a subclass of NEXP.
Let ψ be a sentence in first-order logic. The spectrum of ψ is the set of natural numbers n such that there is a finite model for ψ with n elements.
If the vocabulary for ψ consists only of relational symbols, then ψ can be regarded as a sentence in existential second-order logic (ESOL) quantified over the relations, over the empty vocabulary. A generalised spectrum is the set of models of an ESOL sentence.
is , the set of powers of a prime number. Indeed, with for and for , this sentence describes the set of fields; the cardinality of a finite field is the power of a prime number.
Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine. The theorem was proven by Ronald Fagin in 1974 (strictly, in 1973 in his doctoral thesis).
As a corollary, Jones and Selman showed that a set is in the complexity class NE if it is a spectrum.
One direction of the proof is to show that, for every first-order formula , the problem of determining whether there is a model of the formula of cardinality n is equivalent to the problem of satisfying a formula of size polynomial in n, which is in NP(n) and thus in NE of the input to the problem (the number n in binary form, which is a string of size log(n)).