Abstract
For NP-complete problems, it is a well-known fact that each evaluated variant is checked in polynomial time on von Neumann machines. But the number of variants, as well as the total time for their construction, increases exponentially relative to the length of the input data \(M\) . Associative models can build a variant table with an estimate of \(O(M)\) time and \(O(2^{M})\) memory. Using the cuSTAR library, associative algorithms can be executed on graphics accelerators. This paper presents an associative algorithm to solve the 0-1 knapsack problem, which is implemented on graphics accelerators and achieves a time complexity of \(O(M)\) for limited values of \(M\) . At the same time, the value of \(M\) is not limited by the size of the standard data types. Also, limiting the number of kernels and the length of the variant table leads to an increase in the value of M, at which the algorithm has linear complexity in terms of execution time.
