8 problems

Consider the prefixes $\exists\forall\exists$ and $\exists\exists$, with all quantified variables ranging over $\mathbb{N}$. The prefix $\exists\exists$ is equivalent to the two-va…

Let $R=\\Z[t]$ and $X=\\N$. Define … where each $g_{\alpha(t)}$ is interpreted by … with $g_{\alpha(t)}(x)=0$ when $\alpha(t)=0$. Quantifier-elimination conjecture. Every…

Let $f$ and $g$ be real polynomials in $x_1,\ldots,x_n$ of positive degrees in $x_n$, let $r\in\mathbf{R}[x_1,\ldots,x_{n-1}]$ be their resultant with respect to $x_n$, and suppose…

Quantifier-elimination conjecture. The following are equivalent:

Let $F$ be a field and let $X$ be an algebraic closure of $F$, or let $F$ be an ordered field and let $X$ be its real closure. In either case, quantifier elimination is classically…

Let $K$ be a field. Say that $K$ has almost quantifier elimination if every formula $\phi(x)$, with $x=(x_1,\ldots,x_m)$, is equivalent to a formula $\exists y\,\theta(x,y)$, where…

Let $\alpha$ be a quadratic scalar. NP-hardness conjecture. Deciding $\alpha$-Presburger arithmetic sentences with two alternating blocks of quantifiers, a fixed number of variable…

Let $\mathcal L^*$ be the language obtained by extending the natural language of ordered valued differential rings for $\mathbb{T}$ with a unary function symbol naming the specifie…