Relation between the hardness of a problem and the number of its solutions

MaRDI QIDQ540772zbMATH OpenFDO

Authors Than Quang Khoat

Publication date 3 June 2011

Published in Acta Mathematica Vietnamica (Search for Journal in Brave)

Full work available at URL http://www.math.ac.vn/publications/acta/36/Toc_ACTA_1_36.htm

zbMATH Keywords

bounded integer programming problemhardness of a problemknapsack optimization problemknapsack problemNP-hardnumber of solutionssubset sum problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The Complexity and Distribution of Hard Problems
• scientific article; zbMATH DE number 2044511
• Complexity of counting the optimal solutions
• Complexity of Counting the Optimal Solutions
• scientific article; zbMATH DE number 6146470
• The Number of Solutions Sufficient for Solving a Family of Problems
• scientific article; zbMATH DE number 1775419
• Counting the number of solutions for instances of satisfiability

Cited in

(2)

• Preimage selective trapdoor function: how to repair an easy problem
• The Number of Solutions Sufficient for Solving a Family of Problems

This page was built for publication: Relation between the hardness of a problem and the number of its solutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540772)