logo_acta

Acta Mathematica Vietnamica

RELATION BETWEEN THE HARDNESS OF A PROBLEM AND THE NUMBER OF ITS SOLUTIONS

icon-email THAN QUANG KHOAT

Abstract

In this note, we survey the effect of the number of solutions on solving problems. Theoretically, the number of solutions to a problem cannot help the problem to be easier in the sense of computation. That is, a problem having few solutions may be as easy as the one having many solutions. For the aim of giving some evidences, we show that the Subset sum problem, Knapsack problem and Bounded Integer Programming problem under the assumption that the problem has either no solution or exponentially many solutions are NP-hard. On the other hand, the Knapsack Optimization problem having at most one solution is also NP-hard.