Descriptive complexity may be useful to design programs in a natural declarative way. This is important for parallel computation models such as cellular automata, because designing parallel programs is considered difficult. Our paper establishes logical characterizations of the three classical complexity classes that model minimal time, called real-time, of one-dimensional cellular automata according to their canonical variants. Our logics are natural restrictions of the existential second-order Horn logic. They correspond to the three ways of deciding a language on a square grid circuit of side n according to the three canonical placements of an input word of length n on the grid. Our key tool is a normalization method that transforms a formula into an equivalent formula that faithfully mimics a grid circuit.

We establish an exact logical characterization of linear time complexity of cellular automata of dimension d, for any fixed d: a set of pictures of dimension d belongs to this complexity class iff it is definable in existential second-order logic restricted to monotonic Horn formulas with built-in successor function and d+1 first-order variables. This logical characterization is optimal modulo an open problem in parallel complexity. Furthermore, its proof provides a systematic method for transforming an inductive formula defining some problem into a cellular automaton that computes it in linear time.

A relational structure is d -degree-bounded, for some integer d , if each element of the domain belongs to at most d tuples. In this paper, we revisit the complexity of the evaluation problem of not necessarily Boolean first-order ( FO ) queries over d -degree-bounded structures. Query evaluation is considered here as a dynamical process. We prove that any FO query on d -degree-bounded structures belongs to the complexity class constant-Delay lin , that is, can be computed by an algorithm that has two separate parts: it has a precomputation step of time linear in the size of the structure and then, it outputs all solutions (i.e., tuples that satisfy the formula) one by one with a constant delay (i.e., depending on the size of the formula only) between each. Seen as a global process, this implies that queries on d -degree-bounded structures can be evaluated in total time f (|φ|).(| S | + |φ( S )|) and space g (|φ|).| S | where S is the structure, φ is the formula, φ( S ) is the result of the query and f , g are some fixed functions. Among other things, our results generalize a result of Seese on the data complexity of the model-checking problem for d -degree-bounded structures. Besides, the originality of our approach compared to related results is that it does not rely on the Hanf's model-theoretic technique and is simple and informative since it essentially rests on a quantifier elimination method.

This paper originates from the observation that many classical NP graph problems, including some NP-complete problems, are actually of very low nondeterministic time complexity. In order to formalize this observation, we define the complexity class vertexNLIN, which collects the graph problems computable on a nondeterministic RAM in time O(n), where n is the number of vertices of the input graph G=(V,E), rather than its usual size |V|+|E|. It appears that this class is robust (it is defined by a natural restrictive computational device; it is logically characterized by several simple fragments of existential second-order logic; it is closed under various combinatorial operators, including some restrictions of transitive closure) and meaningful (it contains many natural NP problems: connectivity, hamiltonicity, non-planarity, etc.). Furthermore, the very restrictive definition of vertexNLIN seems to have beneficial effects on our ability to answer difficult questions about complexity lower bounds or separation between determinism and nondeterminism. For instance, we prove that vertexNLIN strictly contains its deterministic counterpart, vertexDLIN, and even that it does not coincide with its complementary class, co-vertexNLIN. Also, we prove that several famous graph problems (e.g. planarity, 2-colourability) do not belong to vertexNLIN, although they are computable in deterministic time O(|V|+|E|).

This article presents two algebraic characterizations and two related complete problems for the complexity class DLIN that was introduced in [E. Grandjean, Ann. Math. Artif. Intell., 16 (1996), pp. 183--236]. DLIN is essentially the class of all functions that can be computed in linear time on a Random Access Machine which uses only numbers of linear value during its computations. The algebraic characterizations are in terms of recursion schemes that define unary functions. One of these schemes defines several functions simultaneously, while the other one defines only one function. From the algebraic characterizations, we derive two complete problems for DLIN under new, very strict, and machine-independent affine reductions.

We consider polynomial time bounded reductions, in particular between k – SAT, SAT and SAT*, in order to obtain the minimal number of variables. As an example we prove that SAT and Unique SAT have, for deterministic algorithms, the same upper bound of the form O( Π c n) for some c > 1, where n is the number of variables of Π. We show that k – Unique SAT is not harder than k – SAT, but not easier than k(r) – SAT (formulas in k – CNF with at most r positive or negative clauses). Finally we present a proof that for each problem in NTlME(n) there is a polynomial reduction to SAT such that the number of variables in f(Π) is only O(n) improving Schnorr–Cook's reduction with O(n log n) variables.

This paper defines and studies a computational model (a random access machine with powerful input/output instructions), and shows that the classes ${\text{DLINEAR}}$ and ${\text{NLINEAR}}$ of problems computable in deterministic (respectively, nondeterministic) linear time in this model of computation are robust and powerful. In particular, ${\text{DLINEAR}}$ includes most of the concrete problems commonly regarded as computable in linear time (such as graph problems, topological sorting, strong connectivity, etc.). Most combinatorial NP-complete problems are in ${\text{NLINEAR}}$. The interest of ${\text{NLINEAR}}$ class is enhanced by the fact that some natural NP-complete problems, for example, “reduction of incompletely specified automata” $({\text{RISA}})$, are ${\text{NLINEAR}}$-complete (consequently, ${\text{NLINEAR}} \ne {\text{ DLINEAR}}$ if and only if ${\text{RISA}} \notin {\text{DLINEAR}}$). This notion strengthens NP-completeness, as this paper argues that propositional satisfiability is not ${\text{NLINEAR}}$ complete.

An NP problem L is linearly NP-complete if each ${\operatorname{NTIME}}(n)$-problem is reducible to L in linear time on a deterministic Turing machine. This implies that $L \notin \operatorname{DTIME}(cn)$ for each $c \geqq 1$. Let R.I.S.A. (Reduction of Incompletely Specified Automata) be the following NP-complete problem (quoted AL7 in the classical book [M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979]. INSTANCE: a positive integer K and an incompletely specified deterministic finite state automaton $A = (Q, \Sigma, \delta, q_0, F)$, where $\delta$ is a “partial” transition function from $Q \times \Sigma $ into Q, and $Q, \Sigma, q_0, F$ are defined as usual. QUESTION: Can $\delta$ be extended to a total transition function from $Q \times \Sigma$ into Q in such a way that the resulting completely specified automaton has an equivalent “reduced automaton” with K or fewer states? It is proved that problem R.I.S.A. is linearly NP-complete. The proof uses a notion of generalized spectrum of a first-order sentence, which has the form $\forall y \bigwedge _{i < p} \mathcal{F}_i (y) = \mathcal{G}_i (y)$ where each $\mathcal{F}_i$, $\mathcal{G}_i$ is a word of the form $f_k \cdots f_2 f_1$, $k \geqq 0$, and each f is a unary function symbol.

Let ${\operatorname{SAT}}_ < (\mathbb{N})$ denote the following problem. Instance. A conjunction $\varphi $ of (in)equalities $t_1 = t_2 $ or $t_1 < t_2 $, where $t_1 $, $t_2 $ are terms of the form $f_1 f_2 \cdots f_s (e)$, where $e \in \mathbb{N}$, $s \geqq 0$ and each $f_i $ is a monadic function symbol. Question. Is $\varphi $ satisfiable on $\mathbb{N}$? Let ${\operatorname{SAT}}_ < ^{2,2} (\mathbb{N})$ denote the following subproblem of ${\operatorname{SAT}}_ < (\mathbb{N})$ defined by the following restriction: we assume that $0 \leqq s \leqq 2$ and each $f_i \in \{ {g_1 ,g_2 } \}$. These two problems are NP-complete. We show that they are solved by a Turing machine using a polynomial number of deterministic steps and only n nondeterministic steps. This is nearly optimal since we prove that any problem in ${\operatorname{NTIME}}(n)$ is reducible in deterministic time $O(n)$ to ${\operatorname{SAT}}_ < (\mathbb{N})$ (respectively, ${\operatorname{SAT}}_ < ^{2,2} (\mathbb{N})$). It follows from the result $ \cup _c {\operatorname{DTIME}}(cn) \subsetneqq {\operatorname{NTIME}}(n)$ of Paul et al. [Proc. 24th Annual IEEE Symposium on Foundations of Computer Sciences, 1983, pp. 429–438] that these problems are not in $ \cup _c {\operatorname{DTIME}}(cn)$. Further, we show that ${\operatorname{SAT}}_ < ^{2,2} (\mathbb{N})$ and ${\operatorname{SAT}}_ < (\mathbb{N})$ belong to $\Sigma _2 (n)$, the class of problems solved in time $O(n)$ by alternating Turing machines using one alternation. They are the first natural problems proved to be in $\Sigma _2 (n) - \cup _c {\operatorname{DTIME}}(cn)$.

The spectrum of a first-order sentence is the set of cardinalities of its finite models. We refine the well-known equality between the class of spectra and the class of sets (of positive integers) accepted by nondeterministic Turing machines in polynomial time. Let $\operatorname{Sp} (d\forall )$ denote the class of spectra of sentences with d universal quantifiers. For any integer $d \geqq 2$ and each set of positive integers, A, we obtain: \[ A \in \operatorname{NTIME} (n^d ) \to A \operatorname{Sp} (d\forall ) \to A \in \operatorname{NTIME} (n^d (\log n)^2 ). \] Further the first implication holds even if we use multidimensional nondeterministic Turing machines. These results hold similarly for generalized spectra. As a consequence, we obtain a simplified proof of a hierarchy result of P. Pudlák about (generalized) spectra. We also prove that the set of primes is the spectrum of a certain sentence with only one variable.

Measuring procedures were developed to assess those lighting characteristics of VDTs which are of importance for visual comfort and for legibility: Luminance oscillation, sharpness, contrasts, stability and dimensions of characters as well as reflections on the display surfaces. 30 different VDT models of various European and US manufacturers disclosed great differences, indicating a big potential for improving the ergonomic qualities of VDTs.