scientific article; zbMATH DE number 3874957
[For the entire collection see Zbl 0537.00025.] The challenging title of this paper hides the presentation of a new method for testing the satisfiabiliy of propositional calculus formulas in conjunctive normal form (CNF's), using methods of polyhedral combinatorics (and hence linear programming techniques). The family of binomial polytopes is defined and it is proven that each clause of a CNF with N variables and p literals per clause has a corresponding face of a binomial polytope \(B_{N,p}\). The article has a special mathematical beauty and it is based on earlier works by the same author.
- A useful transform of standard input data for a classical NP-complete problem
- On the classification of NP-complete problems in terms of their correlation coefficient
- A Natural NP-Complete Problem with a Nontrivial Lower Bound
- On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
- On Hardness of Multilinearization and VNP-Completeness in Characteristic 2
- Roots and (re)sources of value (in)definiteness \textit{versus} contextuality
- The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
- Sublinear P system solutions to NP-complete problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3340499)