8 problems

Let $\Sigma_1$ and $\Sigma_2$ be disjoint signatures, and let ${\mathcal{T}}_1$ and ${\mathcal{T}}_2$ be decidable theories over them. Let ${\mathcal{T}}_1\oplus{\mathcal{T}}_2$ be…

Let $\varphi$ be a [?]

Let $q$-CNFSAT denote the satisfiability problem for conjunctive normal form formulas whose clauses have at most $q$ literals, and let $n$ be the number of variables in the input f…

The iterated logarithm function is defined recursively by … For a positive integer $k$, $k$-SAT asks whether a Boolean formula with $n$ variables has a satisfying assignment. Stron…

Exact-variable Finiteness Conjecture. For every $k\in\mathbb{N}$,

Let $\mathcal{U}\mathcal{HIT}_{\!\delta=k}$ be the class of unsatisfiable hitting clause-sets of deficiency $k$. Let $\operatorname{singind}(F)$ denote the singular index of $F$, a…

Finiteness conjecture. For every deficiency $k\in\mathbb{N}$, there are only finitely many isomorphism types of non-singular unsatisfiable hitting clause-sets.

Variable bound conjecture. Suppose that ${\mathbb{D}}$ is a minimally unsatisfiable $k$-DNF set for some arbitrary but fixed positive integer $k$. Then the number of variables in…