CNF and DNF succinct graph encodings

DOI10.1016/j.ic.2016.06.009zbMath1362.68229OpenAlexW2419633893MaRDI QIDQ515682

Patrick Scharpfenecker, Bireswar Das, Jacobo Toran

Publication date: 16 March 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.06.009

zbMATH Keywords

complexitygraph isomorphismCNFDNFsuccinct encoding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)

Related Items

Computational Complexity of Computing Symmetries in Finite-Domain Planning

Uses Software

• Datalog

Cites Work

• Unnamed Item
• Languages represented by Boolean formulas
• An infinite family of self-diclique digraphs
• Reductions to graph isomorphism
• Symmetric space-bounded computation
• Functions computable in polynomial space
• PP is closed under truth-table reductions
• FSTTCS 2007: Foundations of software technology and theoretical computer science. 27th international conference, New Delhi, India, December 12--14, 2007. Proceedings
• Relationships between nondeterministic and deterministic tape complexities
• The Minimum Oracle Circuit Size Problem.
• Succinct representations of graphs
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• A note on succinct representations of graphs