On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls

DOI10.1155/2009/845804zbMath1182.68091OpenAlexW2008997517WikidataQ58646855 ScholiaQ58646855MaRDI QIDQ1040040

K. Subramani and Vahan Mkrtchyan

Publication date: 23 November 2009

Published in: Journal of Applied Mathematics and Decision Sciences (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/232421

zbMATH Keywords

equivalencecomputational complexitysatisfiabilitypolyhedral structurehull inclusion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (2)

A complexity perspective on entailment of parameterized linear constraints ⋮ On quantified linear implications

Cites Work

• Satisfiability of mixed Horn formulas
• An algorithm for exact satisfiability analysed with the number of clauses as parameter
• Scheduling real-time computations with separation constraints
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A theory of timed automata
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• New methods for 3-SAT decision and worst-case analysis
• Undirected ST-connectivity in log-space
• Symmetric Complementation
• On the Complexity of Computing the Volume of a Polyhedron
• A random polynomial-time algorithm for approximating the volume of convex bodies
• On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
• Scaling Algorithms for the Shortest Paths Problem
• Tools and Algorithms for the Construction and Analysis of Systems
• Theory and Applications of Satisfiability Testing
• The complexity of satisfiability problems
• Frontiers of Combining Systems
• Convex Analysis
• The complexity of theorem-proving procedures
• Bounded model checking using satisfiability solving
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls