scientific article; zbMATH DE number 3874957

MaRDI QIDQ3340499zbMATH OpenFDO

Authors Silvio Ursic

Publication date 1984

zbMATH Keywords

binomial polytopesconjunctive normal formNP-completenesspolyhedral combinatorics

Mathematics Subject Classification ID

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

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