This article is cited 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.

UDC: 510.53+519.61