umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Polynomial in time nonnegative integer solutions of knapsacks and similar problems in R: P=NP?
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2018 (English)In: Mathematical Journal, ISSN 1682-0525, Vol. 18, no 2, p. 47-58Article in journal (Refereed) Published
Abstract [en]

A new result is the well forgotten old one"(A Russian proverb) Annotation. An R-package "nilde" [1] for the enumeration of all existing nonnegative integer solutions of linear Diophantine equations and inequalities and related problems is presented. The software uses the approach based on a generating function of Hardy and Littlewood [2] introduced in 1966 and the algorithm proposed by Voinov and Nikulin [3] in 1997. The package proves to be useful for solving 0-1, bounded and unbounded knapsacks, subset sum problems, integer linear programs, partitioning of natural numbers, etc. The main advantage of the proposed software is that it solves all the above problems in polynomial time. Numerous examples illustrate applications of the package. Strong theoretical and empirical arguments in favor of equality P=NP are presented.

Place, publisher, year, edition, pages
2018. Vol. 18, no 2, p. 47-58
National Category
Natural Sciences Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:umu:diva-160058OAI: oai:DiVA.org:umu-160058DiVA, id: diva2:1323507
Available from: 2019-06-12 Created: 2019-06-12 Last updated: 2019-06-13Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

https://www.researchgate.net/profile/Vassilly_Voinov/publication/327135851_POLYNOMIAL_IN_TIME_NONNEGATIVE_INTEGER_SOLUTIONS_OF_KNAPSACKS_AND_SIMILAR_PROBLEMS_IN_R_PNP/links/5b7ba50c4585151fd123e757/POLYNOMIAL-IN-TIME-NONNEGATIVE-INTEGER-SOLUTIONS-OF-KNAPSACKS-AND-SIMILAR-PROBLEMS-IN-R-PNP.pdf?origin=publication_detail

Authority records BETA

Pya Arnqvist, Natalya

Search in DiVA

By author/editor
Pya Arnqvist, Natalya
By organisation
Department of Mathematics and Mathematical Statistics
Natural SciencesProbability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 30 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf