POLYNOMIAL TIME ALGORITHMS FOR SOLVING NP-COMPLETE PROBLEMS

The paper proposes algorithms with a polynomial time complexity and memory for solving the Subset Sum problem. The algorithm is obtained by using a combination function and mapping, the arguments of which are input data with a given length and a certificate. The work with indices of the input data is based on combination function and the combination generation algorithm. Mapping and combination function help to deal with an exponential time complexity of existing algorithms and solve combinatorial problems with constraints. In fact, the proposed algorithms solve the Millennium problem posed by S.A. Cook in a polynomial time. The proposed algorithms are applicable for input data with a given length together with the certificate with a given value.