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 languageEnglish
Pages (from-to)279–282
JournalInternational Journal on Information Theory and Applications
Volume24
Issue number3
StatePublished - 2017

    Research areas

  • NP-completeness, SUBSET SUM, linear Diophantine equation

ID: 97763677