ХАЛЫҚАPАЛЫҚ АҚПАРАТТЫҚ ЖӘНЕ КОММУНИКАЦИЯЛЫҚ ТЕХНОЛОГИЯЛАР ЖУРНАЛЫ

МЫҢЖЫЛДЫҚ МӘСЕЛЕСІНІҢ ШЕШІМДІЛІГІ: P ЖӘНЕ NP

Авторлар

  • Askar Sinchev JSC "National Information Technologies"
  • Bakhtgerey Sinchev International Information Technology University
  • Nursultan Bakhtgereiuly Nazarbayev University
  • Aksulu Mukhanova Q-university

##plugins.pubIds.doi.readerDisplayName##:

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

Аңдатпа

Бұл жұмыста қажетті теориялық материал Кантор жиындар теориясына негізделген. Біріншіден, кез келген шектеулі жиындар үшін 1-теорема негізінде NP≠P сыныптарының теңсіздігі дәлелденді, осылайша NP сыныбы үшін экспоненциалды алгоритмдердің бар болуы негізделген. Екіншіден, әртүрлі жиындардың күштерін салыстыратын 2-теорема негізінде NP=P сы-
ныптарының теңдігі дәлелденді, бұл қолданбалы маңызы бар және NP-complete тапсырмалары үшін полиномды алгоритмдердің бар болуын негіздейді. Сондай-ақ, табиғи сандардың қосымша жиындарының қосындысы туралы NPcomplete тапсырмаларын, жиынды екі жиынға бөлу (partition problem), тәуелсіз жиын (independent set) күшін k және k-шы шыңының жабыны (vertex cover) туралы NP-complete қосымша жиындары тапсырмасына түрлендіру әдістері ұсынылған. П. Копановтың Бернулли кездейсоқ айнымалыларын генерациялау арқылы қосындысы тең екі жиынды бөлу туралы нақты NP-complete тапсырмасын шешетін контрмысалы қарастырылған және ол осы сыныптардың теңсіздігін дәлелдейтін қатаң дәлел емес.

##plugins.generic.usageStats.downloads##

##plugins.generic.usageStats.noStats##

Автор өмірбаяндары

Bakhtgerey Sinchev, International Information Technology University

Doctor of Technical Sciences, Professor at the Department of Information Systems, International Information Technology University

Nursultan Bakhtgereiuly, Nazarbayev University

Student, Nazarbayev University, School of Engineering and Digital Sciences

Aksulu Mukhanova, Q-university

Candidate of Technical Sciences, Senior Lecturer 

Жүктеулер

Жарияланды

2025-09-15

Дәйексөзді қалай келтіруге болады

Sinchev, A., Sinchev, B., Bakhtgereiuly, N., & Mukhanova, A. (2025). МЫҢЖЫЛДЫҚ МӘСЕЛЕСІНІҢ ШЕШІМДІЛІГІ: P ЖӘНЕ NP. ХАЛЫҚАPАЛЫҚ АҚПАРАТТЫҚ ЖӘНЕ КОММУНИКАЦИЯЛЫҚ ТЕХНОЛОГИЯЛАР ЖУРНАЛЫ, 6(3), 270–277. https://doi.org/10.54309/IJICT.2025.23.3.016

Журналдың саны

Нөмір 6 № 3 (2025): МЕЖДУНАРОДНЫЙ ЖУРНАЛ ИНФОРМАЦИОННЫХ И КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ

Бөлім

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

Лицензия

Авторлық құқық (c) 2025 ХАЛЫҚАPАЛЫҚ АҚПАРАТТЫҚ ЖӘНЕ КОММУНИКАЦИЯЛЫҚ ТЕХНОЛОГИЯЛАР ЖУРНАЛЫ

Creative Commons лицензиясы

Бұл жұмыс Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Дүние жүзінде.

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

##plugins.generic.recommendBySimilarity.heading##

1 2 3 4 5 6 7 8 9 10 > >> 

##plugins.generic.recommendBySimilarity.advancedSearchIntro##