scientific article; zbMATH DE number 3874957

MaRDI QIDQ3340499zbMATH OpenFDO

Authors Silvio Ursic

Publication date 1984

zbMATH Keywords

NP-completenesspolyhedral combinatoricsconjunctive normal formbinomial polytopes

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polytopes and polyhedra (52Bxx) Factorials, binomial coefficients, combinatorial functions (05A10)

Recommendations

• The complexity of satisfiability problems
• Linear programs for constraint satisfaction problems
• A Complexity Index for Satisfiability Problems
• Linear CNF formulas and satisfiability
• A simplified NP-complete satisfiability problem

Cited in

(8)

• A useful transform of standard input data for a classical NP-complete problem
• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• On Hardness of Multilinearization and VNP-Completeness in Characteristic 2
• On the classification of NP-complete problems in terms of their correlation coefficient
• Sublinear P system solutions to NP-complete problems
• Roots and (re)sources of value (in)definiteness \textit{versus} contextuality

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)