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

DOI10.1155/2009/845804zbMath1182.68091WikidataQ58646855 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

equivalence; computational complexity; satisfiability; polyhedral structure; hull inclusion

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C60: Abstract computational complexity for mathematical programming problems

90C09: Boolean programming

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Cites Work

• 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
• 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