Title: Theory / Unimportant / CS / Fundamental / Complexity / Descriptive complexity+14 / Reduction
Tags: fromMath mathToDef mathToSee automaticImplies closed defToCS

Q: [...] [...] [...].
A: The set of FO[+,x] boolean queries; is contained in; the set of boolean queries computable in deterministic logspace
Page: 45
Chapter: 3
Section: 1
Kind: Theo

Smaller0: \(A\models ^I(\theta)\)
Greater0: \(I(\mathcal A)\models \theta\)
Page: 48
Chapter: 3
Variables: \(I:STRUC[\sigma]\to STRUC[\tau]\),
\(\theta\in\mathcal L(\tau)\)
\(\mathcal A\in STRUC[\sigma]\).
Index: 5
Kind: Prop
Smaller to greater: iff
Hide middle: yes

Name: A set of boolean queries closed under first-order reduction
Definition: A set of Boolean queries \(\mathcal C\) such that for any \(B\in\mathcal C\) and \(A\le_{fo}B\), then \(A\in\mathcal C\).
Page: 48
Chapter: 3
Section: 2
Index: 9
Kind: Prop

Smaller0: \(\mathcal C\) is closed under logspace reduction
Greater0: \(\mathcal C\) is closed under \(FO[+,\times]\)-reduction
Page: 49
Chapter: 3
Section: 2
Variables: \(\mathcal C\) a set of boolean queries.
Index: 10
Kind: Prop

Q: REACH is
-[...]
-[...] in [...]
A: NL-complete via \(FO[<]\)-reduction; not definable; \(\text{SO}\exists(\text{monadic})[\tau_g,<]\)-expressible
Page: 51
Chapter: 3
Index: 16
Kind: Theo
Name: REACH
Extra: Theo 13 p 130

Name: REACH
Definition: A directed graph \(G\), and two vertices \(s\) and \(t\) of \(G\), such that there is a path from \(s\) to \(t\) in \(G\)
Page: 51
Chapter: 3
Index: 16
Kind: Theo
Extra: Theo 13 p 130

Name: \(REACH_d\)
Definition: A graph \(G\), and two vertices \(s\) and \(t\) of \(G\), such that there is a path from \(s\) to \(t\) in \(G\), such that all elements of the path admits a single successor.
Page: 53
Chapter: 3
Index: 23
Kind: Theo
Typ: L-complete under \(FO[<]\)-reduction.

Definition: An undirected graph \(G\), and two vertices \(s\) and \(t\) of \(G\), such that there is a path from \(s\) to \(t\) in \(G\)
Page: 50
Chapter: 3
Notation: \(REACH_u\)

Q: [...]
A: The language of graph \(G\), with \(A\) a subset of the vertices, and two vertices \(s\) and \(t\), such that \(P_a^G(s,t)\), where \(P_a^G\) is the smallest relation containing:
-\((x,x)\)
-\((x,y)\) if \(x\) is existential, \(z\) is a successor of \(x\) and it contains \((z,y)\) -
-\((x,y)\) if \(x\) is universal, and for all successors \(z\) of \(x\), it contains \((z,y)\)
Page: 54
Chapter: 3
Section: 4
Index: 26
Kind: Theo
Notation: REACH_a
Q: [...]
A: \(P\)-complete for \(FO[<]\)