On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries

DOI10.1002/malq.200310099zbMath1073.68081OpenAlexW1964809718MaRDI QIDQ4736755

K. Subramani and Vahan Mkrtchyan

Publication date: 6 August 2004

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200310099

zbMATH Keywords

NP-completePSPACE-completelattice point problem2SAT polytopefirst-order queryquantified lattice point problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) 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)

Tightness of sensitivity and proximity bounds for integer linear programs ⋮ Optimal length resolution refutations of difference constraint systems ⋮ Integer feasibility and refutations in UTVPI constraints using bit-scaling ⋮ Improved algorithms for optimal length resolution refutation in difference constraint systems ⋮ Neighborhood persistency of the linear optimization relaxation of integer linear optimization ⋮ A certifying algorithm for lattice point feasibility in a system of UTVPI constraints ⋮ A combinatorial algorithm for Horn programs ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ On integer closure in a system of unit two variable per inequality constraints ⋮ CASCADING RANDOM WALKS ⋮ On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls

This page was built for publication: On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries