Title: Theory / Unimportant / CS / Fundamental / Complexity / Descriptive complexity+14 / Background
Tags: fromMath mathToDef mathToSee automaticImplies algorithm fromAlgorithm hasNotNewEffectReturnsMeaning hasSeenConjDef oldAlgoNewName toBinaryRelation

Name: Vocabulary
Definition: A tuple \[\tau=\langle R_1^{a_1},\dots,R_r^{a_r},c_1,\dots,c_s,f_1^{r_1},\dots,f_t^{r_t}\rangle\] with relation symbols \(R_i\) of arity \(a_i\), function symbols \(f_i\) of arity \(r_i\).
Page: 5
Chapter: 1

Name: The vocabulary of graph with source and terminal node
Definition: \(\langle E^2,s,t\rangle\)
Page: 7
Chapter: 1
Notation: \(\tau_g\)

Name: The vocabulary of binary word
Definition: \(\langle \le^2,S^1\rangle\).
Page: 6
Chapter: 1
Notation: \(\tau_s\)

Name: A relational vocabulary
Definition: A vocabulary without function symbol.
Page: 6
Chapter: 1
Variables: \(\tau\) a vocabulary.

Name: first-order language of \(\tau\)
Definition: the set of formulas built up from the relations and constant symbols of \(\tau\); the logical relation symbol=, the boolean connectives \(\land\), \(\neg\), variables \(VAR=\{x,y,z,\dots,\}\) and quantifier \(\exists\).
Page: 7
Chapter: 1
Variables: \(\tau\) a vocabulary.
Notation: \(\mathcal L(\tau)\)

Name: A bound(free) occurrence of \(x\)
Definition: An occurence of \(x\) which is (respectively, is not) in the scope of a quantifier
Page: 7
Chapter: 1
Variables: \(x\) a variable

Name: A free-variable of \(\phi\)
Definition: A variable such that one of its occurence is free.
Page: 7
Chapter: 1
Variables: \(\phi\) a formula

Definition: \(\mathcal A\) satisfies \(\phi\).
Page: 8
Chapter: 1
Variables: \(\tau\) a vocabulary, \(\mathcal A\) a \(\tau\)-structure and \(\phi\) a \(\tau\in\mathcal L(\tau)\).
Notation: \(\mathcal A\models \phi\)

Name: An interpretation into \(\mathcal A\)
Definition: a map \(i:V\to |\mathcal A|\) where \(V\) is some finite subset of VAR.
Page: 7
Chapter: 1
Variables: \(\tau\) a vocabulary, \(\mathcal A\) a \(\tau\)-structure.

Name: \(c^{\mathcal A} \)
Definition: \(i(c)\)
Page: 7
Chapter: 1
Variables: \(\tau\) a vocabulary,
\(\mathcal A\) a \(\tau\)-structure and
\(i\) an interpretation, and
\(c\in\tau\).
Intuition: yes

Smaller0: \(i(f_j(t_1,\dots,t_{r_j}))\)
Greater0: \(f_j^{\mathcal A}(i(t_1),\dots,i(t_{r_j}))\)
Page: 7
Chapter: 1
Variables: \(\tau\) a vocabulary,
\(\mathcal A\) a \(\tau\)-structure
\(i\) an interpretation.
Smaller to greater: =
Hide middle: yes

Smaller0: \[(\mathcal A,i)\models t_1=t_2\]
Greater0: \[i(t_1)=i(t_2)\]
Page: 7
Chapter: 1
Variables: \(\mathcal A\in STRUC[\tau]\) be a structure and
\(i\) be an interpretation into \(\mathcal A\) whose domain includes all the relevant free variables.
Index: 3
Kind: Def
Smaller to greater: iff
Hide middle: yes

Smaller0: \[(\mathcal A,i)\models R_j(t_1,\dots,t_{a_j})\]
Greater0: \(\langle i(t_1),\dots i(t_{a_j})\rangle\in R_j^{\mathcal A}\)
Page: 7
Chapter: 1
Variables: \(\mathcal A\in STRUC[\tau]\) be a structure and let \(i\) be an interpretation into \(\mathcal A\) whose domain includes all the relevant free variables.
Index: 3
Kind: Def
Smaller to greater: iff
Hide middle: yes

Smaller0: \[(\mathcal A,i)\models \neg\phi\]
Greater0: it is not the case that \[(\mathcal A,i)\models \phi \]
Page: 7
Chapter: 1
Variables: \(\mathcal A\in STRUC[\tau]\) be a structure and let \(i\) be an interpretation into \(\mathcal A\) whose domain includes all the relevant free variables.
Index: 3
Kind: Def
Smaller to greater: iff
Hide middle: yes

Smaller0: \((\mathcal A,i)\models \phi\land\psi\)
Greater0: \((\mathcal A,i)\models \phi\text{ and }(\mathcal A,i)\models \psi \)
Page: 7
Chapter: 1
Variables: \(\mathcal A\in STRUC[\tau]\) be a structure and let \(i\) be an interpretation into \(\mathcal A\) whose domain includes all the relevant free variables.
Index: 3
Kind: Def
Smaller to greater: iff
Hide middle: yes
Suffix Smaller: \(\

Smaller0: \((\mathcal A,i)\models\exists x\phi\)
Greater0: there exists [$]a\in\abs{\mathcal A},(\mathcal A,i,a/x)\models\phi[/$]
Page: 8
Chapter: 1
Variables: \(\mathcal A\in STRUC[\tau]\) be a structure
\(i\) be an interpretation into \(\mathcal A\) whose domain includes all the relevant free variables.
Index: 3
Kind: Def
Smaller to greater: iff
Hide middle: yes

Definition: \(\neg\exists x\neg \phi\).
Page: 8
Chapter: 1
Notation: \(\forall x\phi\)
Index: 3
Kind: Def

Definition: \(\neg(\neg \phi\land\neg \psi)\).
Page: 8
Chapter: 1
Notation: \(\phi\lor\psi\)

Definition: \((\phi\rightarrow\psi)\land (\psi\rightarrow \phi)\).
Page: 8
Chapter: 1
Notation: \(\phi\iff\psi\)

Name: A sentence
Definition: A formula with no free variables.
Page: 8
Chapter: 1

Name: The vocabulary of arithmetic
Definition: \(\langle +^3,\times^3,0,1,max\rangle\).
Page: 9
Chapter: 1
Notation: \(\tau_a\)
Index: 5
Kind: Ex

Definition: There exists an unique \(x\) satisfying \(\phi\).
Page: 10
Chapter: 1
Notation: \(\exists!x\phi\)
Index: 8
Kind: Ex

Definition: \(\exists x.\alpha\land \phi\)
Page: 10
Chapter: 1
Notation: \((\exists x\alpha)\phi\)

Definition: \(\forall x.\alpha\implies \phi\).
Page: 10
Chapter: 1
Variables: \(\phi\) a formula
Notation: \((\forall x\alpha)\phi\)

Page: 11
Implementation: \[(\exists y. x<y)[A(y)\land B(y)\land (\forall z.x<z<y)A(z)\lor B(z)]\]
Section: 1
Variables: \(A\) and \(B\) the two unary relations representing the 1 of the two inputs
Name: carry
Index: 9
Kind: Proposition

Smaller0: a substructure of \(\mathcal B\)
Greater0: \(|\mathcal A|\subseteq |\mathcal B|\), \(R_i^{\mathcal A}=R_i^{\mathcal B}\cap|\mathcal A|^{a_i}\) and \(c_j^{\mathcal A}=c_j^{\mathcal B}\).
Page: 11
Chapter: 1
Variables: \(\mathcal A\) and \(\mathcal B\) be structures of the same relational vocabulary \(\tau\).
Index: 10
Kind: Def
Smaller to greater: iff
Hide middle: yes
Smaller1: \(A\le B\)
Prefix Smaller: We say that \(\mathcal A\) is
Connect Smaller0: , written

Smaller0: \(\phi\) is existential
Greater0: \(\mathcal A\models\phi\) implies \(\mathcal B \models \phi\)
Page: 12
Chapter: 1
Variables: \(\tau\) a vocabulary
\(\mathcal A\le\mathcal B\) structures of vocabulary \(\tau\)
\(\phi\) a first-order sentence.
Hide middle: yes
Smaller1: \(\mathcal A\le\mathcal B\), \(\tau\) relational
Connect Smaller0: ,

Smaller0: \(\phi\) is universal
Greater0: \(\mathcal B\models\phi\) implies \(\mathcal A \models \phi\)
Page: 12
Chapter: 1
Variables: \(\tau\) a vocabulary
\(\mathcal A,\mathcal B\) be structures of vocabulary \(\tau\)
\(\phi\) a first-order sentence.
Hide middle: yes
Smaller1: \(\tau\) relational
Connect Smaller0: and

Definition: The \(y\)th bit in the binary representation of \(x\) is 1.
Page: 13
Chapter: 1
Section: 2
Notation: \(BIT(x,y)\)

Name: the input
Definition: The symbols which are neither numeric relation and constant symbols
Page: 13
Chapter: 1
Section: 2

Q: [...] the other ones are called [...].
A: \(\le\), PLUS, TIMES, BIT, SUC, 0,1 and max; the input
Page: 13
Chapter: 1
Section: 2
Q: [...]
A: The numeric relation and constant symbols

Name: A boolean variable in a first-order formula
Definition: A variable that is restricted to being either 0 or 1.
Page: 14
Chapter: 1
Section: 2
Index: 16
Kind: Def

Q: [...] [...] [...]
A: Bit and <; defines; PLUS and TIMES
Page: 14
Chapter: 1
Section: 2.1
Index: 17
Kind: Theo

Q: is [...]. It is [...]
A: the relation which holds if the number of 1 in the binary representation of \(x\) is \(y\); \(FO[BIT,<]\)-definable
Page: 14
Chapter: 1
Section: 2.1
Index: 18
Kind: Lem
Q: [...]
A: \(BSUM(x,y)\)

Page: 17
Definition: There is a bijective map \(f:|\mathcal A|\to|\mathcal B|\) with the following properties such that \(f(c_i)^{\mathcal A}=f(c_i)^{\mathcal B}\) for all constants \(c_i\) and \(\langle e_1,\dots,e_{a_i}\rangle\in R_i^{\mathcal A} \iff \langle f(e_1),\dots,f(e_{a_i})\rangle\in R_i^{\mathcal B}\) for all \(e_1,\dots,e_{a_i}\in|\mathcal A|\).
Chapter: 1
Section: 3
Variables: \(\tau\) a relational vocabulary and \(\mathcal A,\mathcal B\in\text{Struc}(\tau)\).
Notation: \(\mathcal A\cong \mathcal B\)
Name: Isomorphic \(\tau\)-structures
Kind: Def
Index: 21

Question: Suppose \(\mathcal A\) and \(\mathcal B\) are isomorphic. Then for all sentences \(\phi\), \(\mathcal A\models\phi\iff{}\)
Answer: \(\mathcal B\models \phi\)
Page: 17
Chapter: 1
Section: 3
Variables: \(\tau\) a vocabulary and \(\mathcal A,\mathcal B\in\text{Struc}(\tau)\).
Index: 22
Kind: Prop

Name: A query
Definition: Any mapping \(I:STRUC[\sigma]\to STRUCT[\tau]\) from structures of one vocabulary to structures of another vocabulary, that is polynomially bounded.
Page: 17
Chapter: 1
Variables: \(\sigma,\tau\) vocabularies.
Index: 24
Kind: Def

Name: A first-order query \(I:STRUC[\sigma]\to STRUC[\tau]\)
Definition: an \(r+s+1\)-tuple of formulas \(\phi_0,\phi_1,\dots,\phi_r+\psi_1,\dots,\psi_s\in\mathcal L(\sigma)\). For each structure \(\mathcal A\in STRUC[\sigma]\), these formulas describe a structure \(I(\mathcal A)\in STRUC[\tau]\) whose universe is \(\{(b^1,\dots,b^k)\mid \mathcal A\models \phi_0(b^1,\dots,b^k)\}\). Each relation \(R_i^{I(\mathcal A)}\) is a first-order definable subset of \(|I(\mathcal A)|^{a_i}\), with
\[R_i^{I(\mathcal A)}=\left\{(\langle b_1^1,\dots,b_1^k\rangle,\dots,\langle b^1_{a_i},\dots,b^k_{a_i}\rangle)\in |I(\mathcal A)|^{a_i}\mid \mathcal A\models \phi_i(b^1_1,\dots,b^k_{a_i})\right\}\]
and each constant symbol \(c_j^{I(\mathcal A)}\) is the unique \(\langle b^1,\dots,b^k\rangle \in|I(\mathcal A)|\) such that \(\mathcal A\models \psi_j(b^1,\dots,b^k)\).
Page: 18
Chapter: 1
Variables: \(\sigma\) and \(\tau=\langle R_1^{a_1},\dots,R_r^{a_r},c_1,\dots,c_s\rangle\) be vocabularies and \(k\in\mathbb N\).
Index: 26
Kind: Def

Definition: The set of first-order boolean queries/the set of all first-order queries.
Page: 19
Chapter: 1
Section: 4
Notation: FO/\(\mathcal Q(FO)\)

Question: Then
Answer: \(I_2\circ I_1: STRUC[\sigma_1]\to STRUC[\sigma_3]\) is a \(k_1k_2\)-ary first-order query.
Page: 20
Chapter: 1
Section: 4
Variables: \(\sigma_i\) be vocabularies for \(i\) being 1, 2 or 3.Let \(I_i: STRUC[\sigma_i]\to STRUC[\sigma_{i+1}]\) be a \(k_i\)-ary first-order query.
Index: 28
Kind: Prop

Q: [...] is equal to [...]
A: MSO[<]; regular
Page: 22
Chapter: 1
Section: Historical note
Index: 36
Kind: Theo

Q: [...] equal [...]
A: FO[<] over languages; star-free regular language
Page: 22
Chapter: 1
Section: Historical note
Index: 37
Kind: Theo

Definition: \(M\) halts on the input \(w\).
Page: 24
Chapter: 2
Variables: \(M\) a Turing Machine.
Notation: \(M(w)\downarrow\)

Definition: The set of words accepted \(M\).
Page: 24
Chapter: 2
Variables: \(M\) a turing machine.
Notation: \(L(M)\)

Q: \(R\) is encoded as [...]
A: a binary string \({bin^{\mathcal A} }\) of length \(n^{a_i}\) where \(1\) in a given position indicates that the correpsonding tuple is in \(R_i^{\mathcal A}\).
Page: 24
Chapter: 2
Variables: \(R_i\in\mathcal A\) a relation.
Index: 1
Kind: Def

Q: [...]
A: the concatenation of the binary encoding of the elements of \(\mathcal A\).
Page: 24
Chapter: 2
Variables: \(\tau\) a relational vocabulary
\(\mathcal A\in\text{Struc}(\tau)\).
Index: 1
Kind: Def
Q: [...]
A: Binary encoding of \(\mathcal A\)

Q: [...]
A: for all \(\mathcal A\in STRUC[\sigma]\), \(T(bin(\mathcal A))=bin(I(\mathcal A))\)
Page: 25
Chapter: 2
Variables: \(I:STRUCT [\sigma]\to STRUCT[\tau]\) be a query
\(T\) a Turing machine.
Index: 4
Kind: Def
Q: [...]
A: \(T\) computes \(I\).

Name: A query computable in \(\mathcal C\)
Definition: \(\{\mathcal A,i,a|\text{the $i$th bit of $Q(\mathcal A)$ is $a$} \}\) are computable in \(\mathcal C\).
Page: 26
Chapter: 2
Variables: \(Q\) a query.
Index: 5
Kind: Def

Page: 158
Chapter: 10
Section: 1
Index: 2
Kind: Prop
Name: PSPACE-complete problem via FO reduction
-QSAT Quantified Sat
-Geography
-Given a TM \(M\), a word \(w\) and \(r\in\mathbb N\), decide whether \(M\) accepts \(w\) with \(r\) tape cells.
-\(\text{REACH}_{dl}\)

Name: Geography game
Definition: Let \(G\) a graph. Turn by turn, the player must select an edge, successor to the last edge, and not yet selected.
Page: 158
Chapter: 10
Section: 1
Index: 3
Kind: Ex

Definition: A graph on vertex set \(\{0,1\}\) such that:
-for each vertex \(u\), there is a unique next vertex \(n(u)\), and such that:
-\(n(u)[i]\) is an uniform function of\(u[i-k],\dots,u[i+k]\), where \(u[i]\) is the \(i\)-th bit of \(u\)
Page: 158
Chapter: 10
Section: 1
Variables: \(k,n\in\mathbb N\), \(k\le (\log n)/2-1\)
Notation: \(k\)-local graph

Definition: \(\langle R^1,S^1,T^1\rangle\) where \(S,T\) are source and terminal node, and \(R\) is such that, for each node \(u\), the \(i\)-th bit of its successor is 1 iff \((u_{i-k},\dots,u_{i+k})\in R\).
Page: 159
Chapter: 10
Section: 1
Notation: \(\tau_{l}\)

Definition: Given a \(k\)-local graph encoded as a \(\tau_l\)-structure, decide whether \(T\) is reachable from \(S\).
Page: 159
Chapter: 10
Section: 1
Notation: \(\text{REACH}_{dl}\)

Name: A structure with vocabulary \(\tau\)
Definition: universe the nonempty set \(|\mathcal A|\).
Page: 5
Chapter: 1
Definition2: for each relation \(R_i\), there is \(R_i^{\mathcal A}\subseteq\mathbb |\mathcal A|^{a_i}\), for each constant \(c_i\), there is \(c_i^{\mathcal A}\in\) and for each function \(f_i\), there is \(f_i^{\mathcal A}:|\mathcal A|^{r_i}\to|\mathcal A|\).
Conjdef: A tuple \(\mathcal A=\langle |\mathcal A|,R_1^{a_1},\dots,R_r^{a_r},c_1,\dots,c_s,f_1^{r_1},\dots,f_t^{r_t}\rangle\)

Definition: an abbreviation for \(\neg \phi\lor\psi\).
Page: 8
Chapter: 1
Notation: \(\phi\rightarrow\psi\)

Name: A generic query
Definition: A query \(I\) such that for all isomorphic structures \(\mathcal A,\mathcal B\in STRUCT[\sigma]\), \(I(\mathcal A)\cong I(\mathcal B)\).
Page: 17
Chapter: 1
Section: 4
Context: Descriptive complexity
Index: 24
Kind: Def
Name2: An order-independant query