Main results of Etienne Grandjean

(References of my papers are listed below with numbers of the form [Ji] or [Ci]; additional references by other authors are also listed below after.)

(References of my papers are listed below with numbers of the form [Ji] or [Ci]; additional references by other authors are also listed below after.)

Complexity of the theory of first-order sentences true almost everywhere

- [J1] proves the PSPACE-completeness of the theory Th(S) of first-order sentences, of signature S, true almost everywhere, for each fixed relational signature S.

- Further, [J1] proves several (time or space or mixed time-space) upper and lower bounds for the complexity of this theory : most are optimal modulo open problems in complexity theory such as NTIME(T) =? DSPACE(T) or NSPACE(S) =? DSPACE(S2).

Logical characterizations of nondeterministic precise polynomial or linear time

In a series of improvements [J2, J3, J5, J11, J13], I finally prove that, for each integer d≥1 and each (relational or functional) signature S, a set of S-structures belongs to NTIMERAM(nd) iff this set is definable in existential (functional) second-order logic with only d distinct first-order variables (here, n is the cardinality of the domain of the input structure).

Important things about this result:

- This equivalence is very robust: there are many (natural) equivalent computational (resp. logical) variants of the concerned complexity (resp. definability) classes; it holds whatever the arity of the signature S is, independently of degree d; there is no need of any built-in relation (e.g., no linear order) in the logic;

- This equivalence requires two related conditions: function symbols are needed among the existentially quantified symbols of the formulas; RAMs are required instead of Turing machines: this explains the sequel of my research;

- NLIN is defined in [J8, J9] as the class of sets of unary functional S-structures in NTIMERAM(n).

Note: As a (delicate) corollary, [J11] proves that any language (set of words) in NLIN can be defined in existential (relational) monadic logic with built-in addition, on the domain of indices of the input word (this is an improvement of a result by Jim Lynch: he has proved the same definability result for the class NTIME(n) of Turing machines (instead of RAMs); note that when restricted to built-in linear order instead of addition, this logic only characterizes regular languages [Büchi, Elgot]).

RAMs, DLIN, NLIN and NP-complete problems

Class DLIN and RAMs: The deterministic counterpart of NLIN is defined similarly in [J9]: DLIN is the class of sets of unary functional structures in DTIMERAM(n), where n denotes the cardinality of the domain of the input structure.

Robustness of the RAM model: Papers [C3, J7] are exclusively dedicated to establish the robustness of time complexity on RAMs w.r.t. many variants: set of allowed instructions, use of memory, etc.

"Linear Time Thesis": In [J8, J9], I argue that DLIN is the set of problems computed by linear-time (in an intuitive sense) algorithms. As an important argument, [J9] proves that the sorting problem is in DLIN and hence the class DLIN is essentially insensitive to the presentation of inputs and outputs.

NLIN is also meaningful: I also establish in [J8, J9] that all the 21 problems established by R. Karp (and more generally, most combinatorial NP-complete problems) are in NLIN.

NLIN-complete problems and lower bounds: Papers [J4, J6] exhibit two NLIN-complete problems under reductions in DTIME(n) (linear time of Turing machines); one of them (RISA: Reduction of Incompletely Specified Automata) is the reference problem AL7 of the reference book [GareyJohnson1979]; as a consequence, they are not in DTIME(n).

More classifications of NP problems modulo linear reductions:

- In [J8, J9], I establish that there are many natural NP-complete problems are equivalent each other under linear reductions (in DLIN, or, better, very often in DTIME(n), with or without a fixed number of sortings, the class so-called DTIMESORT(n)).

- The SAT linear class and existential monadic second-order logic: [C6, C7] prove that the class of problems DLIN-reducible to SAT equals the class of problems DLIN-reducible to problems definable in existential monadic (relational) second-order logic with only one first-order variable; this robust subclass of NLIN is called MonadicNLIN; moreover, [C7] proves the following striking result: there is a minimal formula in that logic (existential monadic second-order logic with only one first-order variable) that defines a MonadicNLIN-complete problem, hence an NP-complete problem. This formula is minimal for defining an NP-complete problem under each of 6 syntactic criteria. Moreover, this minimal formula is proved to be unique, up to renaming and symmetries.

Algebraic robustness of DLIN: [J12] establishes a simple algebraic characterization of DLIN (comparable to the one proved by Yuri Gurevich for LogSpace). From this characterization, we derive two rather natural DLIN-complete problems under DTIME(n)-reductions.

Note: Further, both problems are DLIN-complete under affine reductions. [J12] introduces this (very strict, static) notion of affine reduction, that is defined by a system of affine equations, and shows that many natural reductions, including those involved in NLIN-completeness, are affine.

Two classes of graph problems computable in linear in the number of vertices: [J13] introduces two classes of graph problems (presented by adjacency matrices) denoted VertexNLIN and VertexDLIN in the respective nondeterministic and deterministic cases. VertexNLIN is shown to be computationally and logically robust and meaningful: it contains many natural graph problems. Moreover, [J13] proves (by a simple counting method) several structural (nonclosure, separation) properties involving classes DLIN, VertexNLIN and VertexDLIN.

Extension of linear time to enumeration problems

I have introduced a complexity class for enumeration, called LIN-DELAY(lin), : it is the class of enumeration problems computable in two successive phases: a preprocessing phase that runs in linear time in the input size ; an enumeration phase that enumerates the solutions of the problem (one by one, without repetition) with delay (between two successive solutions) and space linear in the size of each expected solution.

I have shown that LIN-DELAY(lin) is a minimal robust complexity class for enumeration problems; we (I and my collaborators) have proved that LIN-DELAY(lin) contains the enumeration extensions of the three classical following model-checking problems :

- MSO queries on classes of bounded tree-width structures : Bagan 2006 [Bagan06]; this is an extension of a classical theorem of Courcelle [Courcelle90, Courcelle92]; see also [Courcelle09] for a variant of this result;

- FO queries on classes of bounded-degree structures [J14, J15] : this is an extension of a theorem of Seese [Seese96];

- a well identified class of acyclic conjunctive queries called connex-acyclic conjunctive queries: see [C8]; this is an extension of the class of acyclic joins [Yannakakis81].

Descriptive complexity of linear time of cellular automata (CA)

Answering a question of J. Mazoyer, I have recently obtained a robust logical characterization of linear time of nondeterministic CAs (paper in preparation), very similar to the one obtained for nondeterministic RAMs : a decision problem (of d-dimensional pictures) is recognized in linear time by a d-dimensional nondeterministic CA iff it is definable in existential relational second-order logic (with a built-in successor function) with only d+1 first-order variables.

REFERENCES

International journals

[J1] E. Grandjean, « Complexity of the first-order theory of almost all finite structures », Information and Control 57 (1983), pp. 180-204.

[J2] E. Grandjean, « The spectra of first-order sentences and computational complexity », SIAM J. Comput. 13 (1984), pp. 356-373.

[J3] E. Grandjean, « Universal quantifiers and time complexity of Random Access Machines », Math. System Theory 18 (1985), pp. 171-187, revised and augmented version of [C1].

[J4] E. Grandjean, « A natural NP-complete problem with a nontrivial lower bound », SIAM J. Comput. 17 (1988), pp. 786-809.

[J5] E. Grandjean, « First-order spectra with one variable », J. Comput. Syst. Sci. 40 (1990), pp. 136-153, revised and augmented version of [C2].

[J6] E. Grandjean, « A nontrivial lower bound for an NP problem on automata », SIAM J. Comput. 19 (1990), pp. 438-451.

[J7] E. Grandjean, « Invariance properties of RAMs and linear time », Computational Complexity 4 (1994), pp. 62-106.

[J8] E. Grandjean, « Linear time algorithms and NP-complete problems », SIAM J. Comput. 23 (1994), pp. 573-597, revised and augmented version of [C4].

[J9] E. Grandjean, « Sorting, linear time and the satisfiability problem », Annals Math. & Artif. Intell. 16 (1996), pp. 183-236.

[J10] E. Grandjean & H. Kleine Büning, « SAT-problems and reductions with respect to the number of variables », J. Logic & Computation 7 (1997), pp. 457-471.

[J11] E. Grandjean & F. Olive, « Monadic logical definability of nondeterministic linear time », Computational Complexity 7 (1998), pp. 54-97.

[J12] E. Grandjean & T. Schwentick, « Machine-independent characterizations and complete problems for deterministic linear time », SIAM J. Comput. 32 (2002), pp. 196-230.

[J13] E. Grandjean & F. Olive, « Graph properties checkable in linear time in the number of vertices », J. Comput. Syst. Sci. 68 (2004), pp. 546-597.

[J14] A. Durand & E. Grandjean, « First-order queries on structures of bounded degree are computable with constant delay », ACM Transactions on Computational Logic (TOCL) 8(4) (2007), 18 pages.

[J15] G. Bagan, A. Durand, E. Grandjean & F. Olive, « Computing the jth solution of a first-order query », RAIRO Theoretical Informatics & Applications 42 (2008), pp. 147-164.

Proceedings of international conferences

[C1] E. Grandjean, « Universal quantifiers and time complexity of Random Access Machines», Logic & Machines 1983, Lect. Notes Comput. Sci. 171 (1984), pp. 366-379.

[C2] E. Grandjean, « First-order spectra with one variable », CSL'86 (Computer Science Logic 1986), Lect. Notes Comput. Sci. 270 (1987), pp. 166-180.

[C3] E. Grandjean & J.-M. Robson, "RAM with compact memory: a realistic and robust model of computation"�, CSL'90 (Computer Science Logic 1990), Lect. Notes Comput. Sci. 533 (1991), pp. 195-233.

[C4] E. Grandjean, « Linear time algorithms and NP-complete problems », CSL'92 (Computer Science Logic 1992), Lect. Notes Comput. Sci. 702 (1993), pp. 248-273.

[C5] E. Grandjean & F. Olive, "Monadic logical definability of NP-complete problems"�, CSL'94 (Computer Science Logic 1994), Lect. Notes Comput. Sci. 933 (1995), pp. 190-204.

[C6] R. Barbanchon & E. Grandjean, "Local problems, planar local problems and linear time", CSL'02 (Computer Science Logic 2002), Lect. Notes Comput. Sci. 2471 (2002), pp. 397-411.

[C7] R. Barbanchon & E. Grandjean, "The minimal logically-defined NP-complete problem", STACS'04 (Symposium on Theoretical Aspects of Computer Sciences 2004), Lect. Notes Comput. Sci. 2996 (2004), pp. 338-349.

[C8] G. Bagan, A. Durand & E. Grandjean, "On acyclic conjunctive queries and constant delay enumeration"�, CSL'07 (Computer Science Logic 2007), Lect. Notes Comput. Sci. 4646 (2007), pp. 208-222.

Additional references

[AhoHopcroftUllman74] A. Aho, J. Hopcroft & J. Ullman, "The design and analysis of computer algorithms"�, Addison-Wesley (1974).

[Bagan06] G. Bagan, "MSO queries on tree decomposable structures are computable with linear delay"�, CSL'06 (Computer Science Logic 2006), Lect. Notes Comput. Sci. 4207 (2006), pp. 167-181.

[BorelloRichardTerrier11] A. Borello, G. Richard & V. Terrier, "A speed-up of oblivious multi-head finite automata by cellular automata"�, STACS'11 (Symposium on Theoretical Aspects of Computer Sciences 2011) (2011), 11 pages.

[CookReckhow73] S. Cook & R. Reckhow, "Time-bounded random access machines"�, J. Comput. System Sci. 7 (1973), pp. 354-375.

[Courcelle90] B. Courcelle, "The monadic second-order logic of graphs. I. Recognizable sets of finite graphs"�, Inf. & Comput. 85(1) (1990), pp. 12-75.

[Courcelle92] B. Courcelle, "The monadic second-order logic of graphs. III: Tree-decomposition, minor and complexity issues"�, ITA 26 (1992), pp. 257-286.

[Courcelle09] B. Courcelle, "Linear delay enumeration and monadic second-order logic"�, Discrete Appl. Math. 157(12) (2009), pp. 2675-2700.

[EbbinghausFlum99] H.-D. Ebbinghaus & J. Flum, "Finite model theory"�, Springer-Verlag, 2nd ed. (1999).

[Fagin74] R. Fagin, "Generalized first-order spectra and polynomial time recognizable sets"�, in "Complexity of Computations"�, R. Karp ed., American Math. Soc., SIAM AMS Proc. VII (1974), pp. 43-73.

[Feder94] R. Feder, "Network flow and 2-satisfiability"�, Algorithmica 11 (1994), pp. 291-319.

[GareyJohnson79] M. Garey & D. Johnson, "Computers and intractability: A guide to the theory of NP-completeness"� (1979), Freeman.

[GrÃ¤del90] E. Grädel, "On the notion of linear time computability"�, Internat. Found. Comput. Sci. 1 (1990), pp. 295-307.

[Gurevich00] Y. Gurevich, "Sequential abstract state machines capture sequential algorithms", ACM Trans. Comput. Logic (TOCL) 1 (2000), pp. 77-111.

[GurevichShelah89] Y. Gurevich & S. Shelah, "Nearly linear time"�, Lect. Notes Comput. Sci. 363 (1989), pp. 108-118.

[Immerman99] N. Immerman, "Descriptive complexity", Springer-Verlag (1999).

[Karp72] R. Karp, "Reducibility among combinatorial problems", IBM Symp. 1972, in "Complexity of computer computations"�, R.E. Miller & J.W. Thatcher (ed.), Plenum Press (1972), pp. 85-103.

[PaulPippengerSzemerediTrotter83] W. Paul, N. Pippenger, E. Szemeredi & W. Trotter, "On determinism versus non-determinism and related problems"�, 24th Symp. Found. of Comput. Sci. (1983), pp. 429-438.

[Seese96] D. Seese, "Linear computable problems and first-order descriptions"�, Math. Structures in Computer Science 6(6) (1996), pp. 505-526.

[Smith71] A. R. Smith III, "Simple computation-universal cellular spaces"�, JACM 18(3) (1971), pp. 339-353.

[Yannakakis81] M. Yannakakis, "Algorithms for acyclic database schemes"�, VLDB'81 (1981), pp. 82-94.