scientific article; zbMATH DE number 3874957

zbMATH Open0548.90049MaRDI QIDQ3340499FDOQ3340499

Authors: Silvio Ursic 

Publication date: 1984

Title of this publication is not available (Why is that?)

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

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)

Cited In (8)

• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• 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
• 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)