Lecture 14 (27.1.97)

Material of this lecture:

• J.A. Makowsky and E. Rosen,
  Invariant Definability, in preparation.

The role of order

• Defining ordered classes of structures.
• FPL is different from ESOL. More precisely: HAM is definable in existential second order logic, but not in fixed point logic. This is not known for ordered HAM (as it would imply that Pis different from NP.
• Invariant definability over orders.
• A class of structures is in P iff it is order-invariantly definable in FPL. Similarly for other complexity classes.
• Order invariant sentences are not recursive.
• Gurevich logics and Gurevich' conjecture: There is no Gurevich Logic capturing P unless P = NP.
• Invariant definability over other K.
• Assume a class of structures is in P iff it is K-invariantly definable in FPL. What can we say about K ?
• Conjecture: If the above is true, then order is parametrically definable in K.
• Evidence for the conjecture, cf. also reference above.