We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given $\Delta _0$-formula $\varphi (x)$; the parameter is the size of $\varphi $. This parameterization focusses attention on instances where n is large compared to the size of $\varphi $. We show unconditionally that this problem does not belong to the parameterized analogue of $\mathsf {AC}^0$. From this we derive that certain natural upper bounds on the complexity of our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that $I\Delta _0$ proves the MRDP theorem in a certain weak sense.

We present an adapted construction of algebraic circuits over the reals introduced by Cucker and Meer to arbitrary infinite integral domains and generalize the $\mathrm{AC}_{\mathbb{R}}$ and $\mathrm{NC}_{\mathbb{R}}^{}$ classes for this setting. We give a theorem in the style of Immerman’s theorem which shows that for these adapted formalisms, sets decided by circuits of constant depth and polynomial size are the same as sets definable by a suitable adaptation of first-order logic. Additionally, we discuss a generalization of the guarded predicative logic by Durand, Haak and Vollmer, and we show characterizations for the $\mathrm{AC}_{R}$ and $\mathrm{NC}_R^{}$ hierarchy. Those generalizations apply to the Boolean $\mathrm{AC}$ and $\mathrm{NC}$ hierarchies as well. Furthermore, we introduce a formalism to be able to compare some of the aforementioned complexity classes with different underlying integral domains.

In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analog of one of the most studied problems in parameterized complexity, the notion of weighted Fagin-definability, which is formulated in terms of satisfaction of first-order formulas with free relation variables. We focus on the parameterized complexity of weighted team definability for a fixed formula $\varphi$ of central team-based logics. Given a first-order structure $\mathcal{A}$ and the parameter value $k\in \mathbb N$ as input, the question is to determine whether $\mathcal{A},T\models \varphi$ for some team T of size k. We show several results on the complexity of this problem for dependence, independence, and inclusion logic formulas. Moreover, we also relate the complexity of weighted team definability to the complexity classes in the well-known W-hierarchy as well as paraNP.

Locality is a property of logics, whose origins lie in the works of Hanf and Gaifman, having their utility in the context of finite model theory. Such a property is quite useful in proofs of inexpressibility, but it is also useful in establishing normal forms for logical formulas. There are generally two forms of locality: (i’) if two structures $\mathfrak {A}$ and $\mathfrak {B}$ realize the same multiset of types of neighborhoods of radius d, then they agree on a given sentence $\Phi $ . Here d depends only on $\Phi $ ; (ii’) if the d-neighborhoods of two tuples $\vec {a}_1$ and $\vec {a}_2$ in a structure $\mathfrak {A}$ are isomorphic, then $\mathfrak {A} \models \Phi (\vec {a}_1) \Leftrightarrow \Phi (\vec {a}_2)$ . Again, d depends on $\Phi $ , and not on $\mathfrak {A}$ . Form (i’) originated from Hanf’s works. Form (ii’) came from Gaifman’s theorem. There is no doubt about the usefulness of the notion of locality, which as seen applies to a huge number of situations. However, there is a deficiency in such a notion: all versions of the notion of locality refer to isomorphism of neighborhoods, which is a fairly strong property. For example, where structures simply do not have sufficient isomorphic neighborhoods, versions of the notion of locality obviously cannot be applied. So the question that immediately arises is: would it be possible to weaken such a condition and maintain Hanf/Gaifman-localities? Arenas, Barceló, and Libkin establish a new condition for the notions of locality, weakening the requirement that neighborhoods should be isomorphic, establishing only the condition that they must be indistinguishable in a given logic. That is, instead of requiring $N_d(\vec {a}) \cong N_d(\vec {b})$ , you should only require $N_d(\vec {a}) \equiv _k N_d(\vec {b})$ , for some $k \geq 0$ . Using the fact that logical equivalence is often captured by Ehrenfeucht–Fraïssé games, the authors formulate a game-based framework in which logical equivalence-based locality can be defined. Thus, the notion defined by the authors is that of game-based locality. Although quite promising as well as easy to apply, the game-based framework (used to define locality under logical equivalence) has the following problem: if a logic $\mathcal {L}$ is local (Hanf-, or Gaifman-, or weakly) under isomorphisms, and $\mathcal {L}'$ is a sub-logic of $\mathcal {L}$ , then $\mathcal {L}'$ is local as well. The same, however, is not true for game-based locality: properties of games guaranteeing locality need not be preserved if one passes to weaker games. The question that immediately arises is: is it possible to define the notion of locality under logical equivalence without resorting to game-based frameworks? In this thesis, I present a homotopic variation for locality under logical equivalence, namely a Quillen model category-based framework for locality under k-logical equivalence, for every primitive-positive sentence of quantifier-rank k.

Abstract prepared by Hendrick Maia.

E-mail: [email protected]

URL: http://repositorio.unicamp.br/jspui/handle/REPOSIP/334956

A Cantor series expansion for a real number x with respect to a basic sequence $Q=(q_1,q_2,\dots )$ , where $q_i \geq 2$ , is a generalization of the base b expansion to an infinite sequence of bases. Ki and Linton in 1994 showed that for ordinary base b expansions the set of normal numbers is a $\boldsymbol {\Pi }^0_3$ -complete set, establishing the exact complexity of this set. In the case of Cantor series there are three natural notions of normality: normality, ratio normality, and distribution normality. These notions are equivalent for base b expansions, but not for more general Cantor series expansions. We show that for any basic sequence the set of distribution normal numbers is $\boldsymbol {\Pi }^0_3$ -complete, and if Q is $1$ -divergent then the sets of normal and ratio normal numbers are $\boldsymbol {\Pi }^0_3$ -complete. We further show that all five non-trivial differences of these sets are $D_2(\boldsymbol {\Pi }^0_3)$ -complete if $\lim _i q_i=\infty $ and Q is $1$ -divergent. This shows that except for the trivial containment that every normal number is ratio normal, these three notions are as independent as possible.

Let L be a computable vocabulary, let XL be the space of L-structures with universe ω and let $f:{2^\omega } \to {X_L}$ be a hyperarithmetic function such that for all $x,y \in {2^\omega }$, if $x{ \equiv _h}y$ then $f\left( x \right) \cong f\left( y \right)$. One of the following two properties must hold. (1) The Scott rank of f (0) is $\omega _1^{CK} + 1$. (2) For all $x \in {2^\omega },f\left( x \right) \cong f\left( 0 \right)$.

Motivated by the search for a logic for polynomial time, we study rank logic (FPR) which extends fixed-point logic with counting (FPC) by operators that determine the rank of matrices over finite fields. While FPR can express most of the known queries that separate FPC from Ptime, almost nothing was known about the limitations of its expressive power.

In our first main result we show that the extensions of FPC by rank operators over different prime fields are incomparable. This solves an open question posed by Dawar and Holm and also implies that rank logic, in its original definition with a distinct rank operator for every field, fails to capture polynomial time. In particular we show that the variant of rank logic ${\text{FPR}}^{\text{*}}$ with an operator that uniformly expresses the matrix rank over finite fields is more expressive than FPR.

One important step in our proof is to consider solvability logic FPS which is the analogous extension of FPC by quantifiers which express the solvability problem for linear equation systems over finite fields. Solvability logic can easily be embedded into rank logic, but it is open whether it is a strict fragment. In our second main result we give a partial answer to this question: in the absence of counting, rank operators are strictly more expressive than solvability quantifiers.

We study the expressive power of independence-friendly quantifier prefixes composed of universal $\left( {\forall x/X} \right)$, existential $\left( {\exists x/X} \right)$, and majority quantifiers $\left( {Mx/X} \right)$. We provide four quantifier prefixes that can express NP hard properties and show that all quantifier prefixes capable of expressing NP-hard properties embed at least one of these four quantifier prefixes. As for the quantifier prefixes that do not embed any of these four quantifier prefixes, we show that they are equivalent to a first-order quantifier prefix composed of $\forall x$, $\exists x$, and Mx. In unison, our results imply a dichotomy result: every independence-friendly quantifier prefix is either decidable in LOGSPACE or NP hard.