scientific article
From MaRDI portal
Publication:3194807
zbMath1327.68137arXiv1312.4524MaRDI QIDQ3194807
Publication date: 20 October 2015
Full work available at URL: https://arxiv.org/abs/1312.4524
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexitygraph connectivityBoolean satisfiabilityPSPACE-completenessdichotomy theoremsBoolean CSPs
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (11)
Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Reconfiguration on nowhere dense graph classes ⋮ The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ On the Structure of Solution-Graphs for Boolean Formulas ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ Introduction to reconfiguration ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1
This page was built for publication:
