Title: Theory / Unimportant / CS / Fundamental / Complexity / Descriptive complexity+14 / Second order
Tags: fromMath mathToDef mathToSee closed defToProb

Q: [...] means [...]
A: \(\forall A^r\phi\); for all \(r\)-ary relation \(A\), \(\phi\)
Page: 113
Chapter: 7
Section: 1
Variables: \(\phi\) a formula.

Definition: The set of second order formula over vocabulary \(\tau\).
Page: 113
Chapter: 7
Section: 1
Variables: \(\tau\) a vocabulary.
Notation: SO(\(\tau\))

Definition: The set of second order formula over vocabulary \(\tau\), with the second order quantifications restricted to existential quantification.
Page: 113
Chapter: 7
Section: 1
Variables: \(\tau\) a vocabulary.
Notation: \(\texttt{SO}\exists(\tau)\)

Smaller0: \(\texttt{NTIME}[n^k]\)
Greater0: \(\texttt{SO}\exists(\text{arity } k)\)
Page: 117
Chapter: 7
Section: 2
Variables: \(k\ge 1\)
Index: 11
Kind: Theo
Smaller to greater: \(\subseteq\)
Name: Lynch's theorem
Greater to smaller: \(\supseteq\)

Question: (3-)SAT and 3-color is
Answer: NP-complete for FO[<,bit]-reduction
Page: 119
Chapter: 7
Section: 3
Index: 16
Kind: Theo

Smaller0: \(S=\texttt{MOD}[\Phi]\) for some \(\phi\in\Sigma_k^{\text{SO} }\), second order formula with \(k-1\) alternation, beginning by existential formula
Greater0: \(S=\{x\mid (\exists y_1.|y_1|\le |x|^c)(\forall y_2.|y_2|\le |x|^c)\dots(Q_k y_k.|y_k|\le |x|^c) R(x,\overline y)\) where \(R\) is a deterministic polynomial-time predicate on \(k+1\) tuples of binary strings and \(c\) constant
Page: 121
Chapter: 7
Section: 4
Variables: \(\tau\) a vocabulary, \(S\subseteq\texttt{STRUC}[\tau]\) a boolean query, and \(k\ge 1\)
Index: 21
Kind: Theo
Smaller to greater: iff
Extra: jeu ?
Greatest: \(S\in\texttt{ATIME-ALT}[n^{O(1)},k]=S\in\Sigma_k^p\)

Smaller0: \(\texttt{SO}[t(n)] \)
Greater0: \(\texttt{CRAM-PROC}[t(n),2^{n^{O(1)} }]\)
Page: 123
Chapter: 7
Section: 4
Variables: \(t\) time constructible
Index: 28
Kind: Cor
Smaller to greater: =
Hide middle: yes

Name: The second-order (monadic) \(c\)-color, \(m\)-move game on \(\mathcal A,\mathcal B\)
Definition: Samson chooses \(c\)-monadic relations \(C_1^{\mathcal A},C_2^{\mathcal A},\dots,C_c^{\mathcal A}\) on \(|\mathcal A|\). Dalilah answers with \(c\)-monadic relations \(C_1^{\mathcal B},C_2^{\mathcal B},\dots,C_c^{\mathcal B}\) on \(|\mathcal B|\). Next they play \[\mathcal G_m((\mathcal A, C_1^{\mathcal A},C_2^{\mathcal A},\dots,C_c^{\mathcal A}),(\mathcal B,C_1^{\mathcal B},C_2^{\mathcal B},\dots,C_c^{\mathcal B}))\]
Page: 125
Chapter: 8
Section: 1
Variables: \(\tau\) a vocabulary, \(\mathcal A,\mathcal B\) two \(\tau\)-structures, \(c,m\in\mathbb N\)
Kind: Def

Smaller0: for any formula \(\Phi\equiv (\exists C^1_1\dots C ^1_c)(\phi)\) with \(\phi\) first-order, of quantifier rank \(m\), \(\mathcal A\models \Phi\implies\mathcal B\models \Phi\)
Greater0: Delilah has a winning strategy for the second-order (monadic) \(c\)-color, \(m\)-move game on \(\mathcal A,\mathcal B\)
Page: 125
Chapter: 8
Section: 1
Variables: \(\tau\) a vocabulary,
\(\mathcal A,\mathcal B\) two \(\tau\)-structures,
\(c,m\in\mathbb N\)
Index: 2
Kind: Theo
Smaller to greater: iff

Q: [...] is:
[...]
A: The Ajtai-Fagin game on \(I\); Samson chooses \(c,m\in\mathbb N\)
-Delilah chooses a structure \(\mathcal A\in\texttt{STRUC}[\tau]\) such that \(\mathcal A\in I\)
-Samson chooses \(c\)-monadic relations \(C_1^{\mathcal A},C_2^{\mathcal A},\dots,C_c^{\mathcal A}\) on \(|\mathcal A|\).
-Dalilah chooses a structure \(\mathcal B\in\texttt{Struc}[\tau]\setminus I\) and \(c\)-monadic relations \(C_1^{\mathcal B},C_2^{\mathcal B},\dots,C_c^{\mathcal B}\) on \(|\mathcal B|\).
-Next they play \[\mathcal G_m((\mathcal A, C_1^{\mathcal A},C_2^{\mathcal A},\dots,C_c^{\mathcal A}),(\mathcal B,C_1^{\mathcal B},C_2^{\mathcal B},\dots,C_c^{\mathcal B}))\]
Page: 127
Chapter: 8
Section: 1
Variables: \(\tau\) a vocabulary,
\(I\subseteq\mathbb{STRUC}[\tau]\)
Index: 4
Kind: Def

Smaller0: Delilah has a winning strategy for the Ajtai-Fagin game on \(I\)
Greater0: \(I\not\in\texttt{SO}\exists(monadic)\)
Page: 127
Chapter: 8
Section: 1
Variables: \(\tau\) a vocabulary, \(I\subseteq\mathbf{STRUC}[\tau]\)
Index: 5
Kind: Theo
Smaller to greater: iff
Hide middle: yes

Name: \(\text{SO}\exists\)(monadic)
Page: 129
Section: 1
Chapter: 8
Index: 9, 10, 12
Variables: \(G\) a connected graph.
Kind: Cor
Not: not
Under: complementation
Under2: first-order quantification
Condition2: only existential
Under3: quantifier-free reductions

Page: 130
Section: 2
Chapter: 8
Name: REACH_u
Returns: Whether there is a path from \(s\) to \(t\) in \(G\).
Input: An undirected graph \(G\), and two vertices \(s\) and \(t\) of \(G\)
Kind: Prop
Index: 11
Logical complexity: \(\text{SO}\exists(\text{monadic})[\tau_g,<]\)-definable

Question: 139-143
Answer: manquant
Page: 130
Chapter: 8
Section: 2
Index: 11
Kind: Prop

Definition: SO-Horn = SO\(\exists\)-Horn
Page: 153
Chapter: 9
Section: 6
Index: 28
Kind: Lem

Definition: SO-Krom = SO\(\exists\)-Krom
Page: 153
Chapter: 9
Section: 6
Index: 28
Kind: Lem

Question: SO-Horn =
Answer: P.
Page: 153
Chapter: 9
Section: 6
Index: 32
Kind: Theo

Question: SO-Krom =
Answer: NL.
Page: 153
Chapter: 9
Section: 6
Index: 32
Kind: Theo

Name: A complete formula of \(\mathcal L\)
Definition: A consistent formula \(\phi\) such that, for each consistent formula \(\psi\in\mathcal L\) that implies \(\phi\), then \(\phi\iff \psi\)
Page: 127
Chapter: 8
Section: 1
Variables: \(\mathcal L\) a language
Index: 3
Kind: Def

Smaller0: \(\texttt{NP}\)
Greater0: \(\texttt{SO}\exists\Pi_1[<,bit] \)
Page: 115
Chapter: 7
Section: 2
Index: 8
Kind: Theo
Smaller to greater: =
Smallest: \(\texttt{SO}\exists[<,bit]\)
Intermediate: \(\texttt{SO}\exists-Horn\)

Page: 130
Section: 2
Chapter: 8
Name: REACH_u
Returns: Whether there is a path from \(s\) to \(t\) in \(G\).
Input: An undirected graph \(G\), and two vertices \(s\) and \(t\) of \(G\)
Kind: Prop
Index: 11