Pages that link to "Item:Q3489984"
From MaRDI portal
The following pages link to Reachability is harder for directed than for undirected finite graphs (Q3489984):
Displayed 32 items.
- One unary function says less than two in existential second order logic (Q286970) (← links)
- Finite-model theory -- A personal perspective (Q688663) (← links)
- Existential MSO over two successors is strictly weaker than over linear orders (Q837190) (← links)
- The functional dimension of inductive definitions (Q1193414) (← links)
- The quantifier structure of sentences that characterize nondeterministic time complexity (Q1198956) (← links)
- On winning strategies in Ehrenfeucht-Fraïssé games (Q1269907) (← links)
- Arity bounds in first-order incremental evaluation and definition of polynomial time database queries (Q1278038) (← links)
- Verifiable properties of database transactions (Q1281498) (← links)
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures (Q1336623) (← links)
- Reachability and the power of local ordering (Q1367543) (← links)
- The closure of monadic NP (Q1577017) (← links)
- Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs (Q1686112) (← links)
- Bounds in the propagation of selection into logic programs (Q1813949) (← links)
- The monadic second-order logic of graphs. VIII: Orientations (Q1842126) (← links)
- Generalized quantifiers and pebble games on finite structures (Q1892941) (← links)
- Cutting planes, connectivity, and threshold logic (Q1908818) (← links)
- On winning Ehrenfeucht games and monadic NP (Q1919539) (← links)
- Arity and alternation in second-order logic (Q1919768) (← links)
- Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification (Q2232597) (← links)
- Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents (Q2255227) (← links)
- The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws (Q2283277) (← links)
- The monadic theory of finite representations of infinite words (Q2379951) (← links)
- Characterizability in Horn Belief Revision (Q2835894) (← links)
- The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture (Q2947167) (← links)
- On Linear Secret Sharing for Connectivity in Directed Graphs (Q3540044) (← links)
- Weakly useful sequences (Q4645195) (← links)
- Graph Connectivity, Monadic NP and built-in relations of moderate degree (Q4645196) (← links)
- Fifty years of the spectrum problem: survey and new results (Q4902770) (← links)
- The complexity of graph connectivity (Q5096823) (← links)
- Shortest-path queries in static networks (Q5176178) (← links)
- First order quantifiers in monadic second order logic (Q5311712) (← links)
- Comparing the power of monadic NP games (Q6064292) (← links)