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

zbMATH Open1221.68096MaRDI QIDQ540772FDOQ540772

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

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

zbMATH Keywords

knapsack problemNP-hardnumber of solutionsbounded integer programming problemhardness of a problemknapsack optimization problemsubset sum problem

Mathematics Subject Classification ID

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

Cited In (2)

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

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)