|
Prikladnaya Diskretnaya Matematika, 2012, Number 3(17), Pages 96–102
(Mi pdm380)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Computational Methods in Discrete Mathematics
About some features of the transformed problems images
D. M. Murin Demidov Yaroslavl State University, Yaroslavl, Russia
Abstract:
One of the way to prove the NP-completeness of a problem is to transform in it polynomially a problem the NP-completeness of which we can prove. Herewith we pay less attention to the research of the received image features. In 1985 Lagarias and Odlyzko offered a method for solving knapsack NP-complete problem that gives a true decision for “near all” knapsacks with the density less than $0.6463\dots$ In this paper, we consider the following question: in which knapsack problems area (with regard to the knapsacks density) we can place, while proving the NP-completeness, the images of the problems such as $3$-SAT, Colouring, Exact cover.
Keywords:
NP-completeness, Lagarias–Odlyzko method, knapsack problem.
Citation:
D. M. Murin, “About some features of the transformed problems images”, Prikl. Diskr. Mat., 2012, no. 3(17), 96–102
Linking options:
https://www.mathnet.ru/eng/pdm380 https://www.mathnet.ru/eng/pdm/y2012/i3/p96
|
Statistics & downloads: |
Abstract page: | 187 | Full-text PDF : | 90 | References: | 35 | First page: | 1 |
|