«P қарсы NP» теоремасын тәжірибе жүзінде дәлелдеу туралы
DOI:
https://doi.org/10.26577/JMMCS202512735Кілттік сөздер:
P қарсы NP, теорема, дәлелдеу, күрделілік, қолданбалы математикаАннотация
Біз кеңейтілген операторлар ішінде алгоритм ұғымдарын пайдалана отырып, md-DFA есебін шешудің қарапайым және интуитивті алгоритмін ұсынамыз, біздің әдіс квадраттық көпмүшелік уақытты көрсетеді және осылайша көпмүшелік және көпмүшелік емес сыныптар арасындағы эквиваленттілігін дәлелдейді, сонымен қатар біз автоматтандырылған есептің минималды бос еместігін модификацияланған ішкі уақыт өнімін құру арқылы шешуге болатындығын көрсеттік. жады мен уақыттың факторлық өлшеміне әкелетін автомат, бұл жұмыста біз сонымен қатар көптеген транзакцияланбайтын бар мысалдарды қолдандық және оларды көпмүшелік уақытта есептедік, бұл біздің алгоритміміз NP-толық есепті дерлік сызықтық көпмүшелік уақытта шешетініне кепілдік береді, сонымен қатар алгоритмдік тәсіл арқылы өнімнің автоматтары мәселесін болдыртпадық, біз бұған дейін дәлелдеме берген мәселені де талқыладық. жаһандық жергілікті өсімге жалпы математикадағы соңғылық терминімен сәйкес келетін «P қарсы NP» теоремасын шешудің негізгі дәлелі ретінде де берілген.
