10 problems

Let $\Upsilon$ be a finite vocabulary, and consider finite structures over $\Upsilon$ without a distinguished linear ordering of their underlying sets. A logic in the relevant sens…

CMSO-fragment conjecture.

An extensional ESO sentence $\Phi$ defines a decision problem by asking whether the sentence holds on the input structure. Extensional ESO NP-intermediate conjecture. There is an e…

Extensional ESO is a logical formalism whose sentences define decision problems through existential second-order quantification with extensionality constraints. Extensional ESO dic…

Hardness dichotomy conjecture. All sets $S=[S]$ are either $\Sigma^0_3$-hard or $\Pi^0_3$-hard.

Semiring CFI conjecture. By lifting the well-known CFI-construction to semirings, one can show that there is no semiring for which first-order logic, and even fixed point logic, is…

Fix a standard encoding of structures by binary strings. A Turing machine $M$ is generic if the set of structures $S$ such that $M$ accepts the standard string encoding of $S$ is c…

Let $\mathrm{PLH}$ denote the poly-logarithmic hierarchy, and let $\mathrm{PolyLogSpace}$ be the corresponding poly-logarithmic space complexity class. Let $\mathrm{P}$ denote dete…

A graph class admits $\mathsf{IFP}+C$-definable canonisation if there is a canonisation procedure for graphs in the class that is definable in inflationary fixed-point logic with c…

A logic is intended to capture $\textsf{PTIME}$ when its sentences define exactly the polynomial-time decidable properties of finite structures, with effective translation from sen…