Reachability is harder for directed than for undirected finite graphs

DOI10.2307/2274958zbMath0708.03016OpenAlexW2023552332MaRDI QIDQ3489984

Miklós Ajtai, Ronald Fagin

Publication date: 1990

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2274958

zbMATH Keywords

reachability problemEhrenfeucht-Fraïssé gamesexistential monadic second-order sentenceundirected reachability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15) Connectivity (05C40)

Related Items (32)

One unary function says less than two in existential second order logic ⋮ The monadic second order logic of graphs. VI: On several representations of graphs by relational structures ⋮ Existential MSO over two successors is strictly weaker than over linear orders ⋮ Generalized quantifiers and pebble games on finite structures ⋮ The monadic theory of finite representations of infinite words ⋮ First order quantifiers in monadic second order logic ⋮ Weakly useful sequences ⋮ Cutting planes, connectivity, and threshold logic ⋮ Reachability and the power of local ordering ⋮ On winning Ehrenfeucht games and monadic NP ⋮ Arity and alternation in second-order logic ⋮ The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture ⋮ The complexity of graph connectivity ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ Comparing the power of monadic NP games ⋮ On Linear Secret Sharing for Connectivity in Directed Graphs ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Fifty years of the spectrum problem: survey and new results ⋮ Graph Connectivity, Monadic NP and built-in relations of moderate degree ⋮ The functional dimension of inductive definitions ⋮ The quantifier structure of sentences that characterize nondeterministic time complexity ⋮ Finite-model theory -- A personal perspective ⋮ Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents ⋮ Shortest-path queries in static networks ⋮ The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws ⋮ Bounds in the propagation of selection into logic programs ⋮ On winning strategies in Ehrenfeucht-Fraïssé games ⋮ Arity bounds in first-order incremental evaluation and definition of polynomial time database queries ⋮ Verifiable properties of database transactions ⋮ Characterizability in Horn Belief Revision ⋮ The closure of monadic NP ⋮ The monadic second-order logic of graphs. VIII: Orientations

Cites Work

• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Upper and lower bounds for first order expressibility
• Structure and complexity of relational queries
• Relationships between nondeterministic and deterministic tape complexities
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Second-order and Inductive Definability on Finite Structures
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Monadic generalized spectra
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Reachability is harder for directed than for undirected finite graphs