Аннотация
В данной работе необходимый теоретический материал базируется на теории множеств Кантора. Во-первых, доказано неравенство классов на основе теоремы1 для произвольных конечных множеств и тем самым обосновано существование экспоненциальных алгоритмов для класса , во-вторых, доказано равенство классов на базе предложенной теоремы2 сравнения мощностей разных множеств, имеющей прикладную значимость, и обосновано существование полиномиальных алгоритмов для NP-completeзадач. Предложены методы сведения NP-complete задач о сумме подмножества натуральных чисел, о разбиении множества на два подмножества (partitionprob-lem), о независимом множестве (independentset) мощности k и о k-вершинном покрытии (vertexcover) к NP-complete задаче о сумме подмножества (subsetsum). Рассмотрен контрпример П. Копанова, решающий конкретную NP-com-plete задачу о разбиении множества на два подмножества с равными суммами при генерации случайных величин Бернулли, иононе является строгим доказательством неравенства этих классов.