МЕЖДУНАРОДНЫЙ ЖУРНАЛ ИНФОРМАЦИОННЫХ И КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ

О ПРОБЛЕМЕ ТЫСЯЧЕЛЕТИЯ ДЛЯ КЛАССОВ P & NP

Авторы

  • Б.К. Синчев МУИТ https://orcid.org/0000-0001-8557-8458
  • О. Danchenko доктор технических наук, профессор, ЧЕРКАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ (Украина)

DOI:

https://doi.org/10.54309/IJICT.2023.14.2.009

Ключевые слова:

Ключевые слова: классы P, NP, NP-complete, множество, подмножество, мощность, время, пространство

Аннотация

Аннотация. Проблема равенства классов P и NP сведена к решению задачи о сумме подмножеств. Доказана  линейная (либо квадратичная ) разрешимость поставленной задачи, которая принадлежит классу NP-complete. Таким образом, линейная разрешимость и полнота subset sum problem подтверждают равенство классов P и NP.

Скачивания

Данные скачивания пока недоступны.

Загрузки

Опубликован

2023-06-15

Как цитировать

Sinchev, B., & О. Danchenko. (2023). О ПРОБЛЕМЕ ТЫСЯЧЕЛЕТИЯ ДЛЯ КЛАССОВ P & NP. МЕЖДУНАРОДНЫЙ ЖУРНАЛ ИНФОРМАЦИОННЫХ И КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ, 4(2), 94–101. https://doi.org/10.54309/IJICT.2023.14.2.009

Выпуск

Том 4 № 2 (2023): МЕЖДУНАРОДНЫЙ ЖУРНАЛ ИНФОРМАЦИОННЫХ И КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ

Раздел

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

Лицензия

Copyright (c) 2023 МЕЖДУНАРОДНЫЙ ЖУРНАЛ ИНФОРМАЦИОННЫХ И КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial-NoDerivatives» («Атрибуция — Некоммерческое использование — Без производных произведений») 4.0 Всемирная.

https://creativecommons.org/licenses/by-nc-nd/3.0/deed.en