SOLVABILITY OF THE MILLENNIUM PROBLEM: P VS NP
DOI:
https://doi.org/10.54309/IJICT.2025.23.3.016Ключевые слова:
P class, NP class, NP-complete class, set, subset, time complexity, space complexity, countability, equinumerosity, Diophantine equation, algorithmАннотация
В данной работе необходимый теоретический материал базируется на теории множеств Кантора. Во-первых, доказано неравенство классов P и NP на основе теоремы1 для произвольных конечных множеств и тем самым обосновано существование экспоненциальных алгоритмов для класса , во-вторых, доказано равенство классов P и NP на базе предложенной теоремы2 сравнения мощностей разных множеств, имеющей прикладную значимость, и обосновано существование полиномиальных алгоритмов для NP-complete задач. Предложены методы сведения NP-complete задач о сумме подмножества натуральных чисел, о разбиении множества на два подмножества (partition problem), о независимом множестве (independent set) мощности k и о k-вершинном покрытии (vertex cover) к NP-complete задаче о сумме подмножества (subset sum). Рассмотрен контрпример П. Копанова, решающий конкретную NP-complete задачу о разбиении множества на два подмножества с равными суммами при генерации случайных величин Бернулли и оно не является строгим доказательством неравенства этих классов.
Скачивания
Загрузки
Опубликован
Как цитировать
Выпуск
Раздел
Лицензия
Copyright (c) 2025 МЕЖДУНАРОДНЫЙ ЖУРНАЛ ИНФОРМАЦИОННЫХ И КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial-NoDerivatives» («Атрибуция — Некоммерческое использование — Без производных произведений») 4.0 Всемирная.
https://creativecommons.org/licenses/by-nc-nd/3.0/deed.en