Given a CNF formula $φ$ with clauses $C_1, \dots, C_m$ over a set of variables $V$, a truth assignment $\mathbf{a} : V \to \{0, 1\}$ generates a binary sequence $σ_φ(\mathbf{a})=(C_1(\mathbf{a}), \ldots, C_m(\mathbf{a}))$, called a signature of $φ$, where $C_i(\mathbf{a})=1$ if clause $C_i$ evaluates to 1 under assignment $\mathbf{a}$, and $C_i(\mathbf{a})=0$ otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, Bérczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard. They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.e., those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNFs.

Many AI-related reasoning problems are based on the problem of satisfiability of propositional formulas with some cardinality-minimality condition. While the complexity of the satisfiability problem (SAT) is well understood when considering systematically all fragments of propositional logic within Schaefer’s framework, this is not the case when such minimality condition is added. We consider the CardMinSat problem, which asks, given a formula φ and an atom x, whether x is true in some cardinality-minimal model of φ. We completely classify the computational complexity of the CardMinSat problem within Schaefer’s framework, thus paving the way for a better understanding of the tractability frontier of many AI-related reasoning problems. To this end we use advanced algebraic tools.

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.

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|).