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

zbMath1221.68096MaRDI QIDQ540772

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

number of solutionsknapsack problemNP-hardbounded integer programming problemhardness of a problemknapsack optimization problemsubset sum problem

Mathematics Subject Classification ID

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

Related Items (1)

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