The problem SUBSET SUM Garey, Johnson, [1979] may be interpreted as the problem of solvability in {0, 1} numbers checking of a linear Diophantine equation with positive coefficients and constant term. This problem is the one of the most simply formulated mathematical problems for which it is proved that it is NP-complete. Its essential restriction under which it remains to be NP-complete are offered in the paper.
Original language
English
Pages (from-to)
279–282
Journal
International Journal on Information Theory and Applications
Volume
24
Issue number
3
State
Published - 2017
Research areas
NP-completeness, SUBSET SUM, linear Diophantine equation