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

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)