Skip to main content

New answers tagged

5 votes

Computational complexity of the elementary theory of finite fields

By Proposition 13 in Benedikt and Hrushovski, the theory of finite fields has nonelementary complexity (it is harder than $k$-times iterated exponential time for all constants $k$). Apparently, the ...
Emil Jeřábek's user avatar
0 votes

Is there a logic without induction that captures much of P?

Let $L \subset K$ be two signatures and $\mathcal{L,K}$ be a nonempty classes of $L$-structures and $K$-structures respectively such that every structure in $\mathcal{L}$ has an expansion in $\...
Siddharth's user avatar
  • 851

Top 50 recent answers are included