Please use this identifier to cite or link to this item: https://elib.belstu.by/handle/123456789/26631
Full metadata record
DC FieldValueLanguage
dc.contributor.authorГерман, Юлия Олеговнаru
dc.contributor.authorГерман, Олег Витольдовичru
dc.date.accessioned2018-11-12T05:30:56Z-
dc.date.available2018-11-12T05:30:56Z-
dc.date.issued2018-
dc.identifier.citationГерман, Ю. О. О несоответствии между распознаванием языка за полиномиальное время и тотальной полиномиальностью распознавателя / Ю. О. Герман, О. В. Герман // Труды БГТУ. Сер. 3, Физико-математические науки и информатика. - Минск : БГТУ, 2018. - № 2 (212). - С. 119-123.ru
dc.identifier.urihttps://elib.belstu.by/handle/123456789/26631-
dc.description.abstractПриводимые в статье рассуждения устанавливают разницу между тотальной полиномиальностью распознающей машины и полиномиальной сложностью реализуемого ею алгоритма. Проблема связана с отождествлением выводов и доказательств, что не всегда допустимо. Кроме того, нужно иметь в виду, что доказательство становится некорректным, если оно доказывает предикат, являющийся характеристической функцией изменяющегося в процессе доказательства множества. Таким образом, множество доказательств, вообще говоря, не следует отождествлять с множеством корректно построенных выводов. Применительно к теории вычислительной сложности заметим, что трудности доказательства P ≠ NP могут быть напрямую связаны с рассматриваемыми в данной статье проблемами теории доказательств. Возникает идея сведения языка, распознаваемого некоторой детерминированной машиной М за полиномиальное время, при условии, что для М нет доказательства тотальной полиномиальности, к языку Выполнимость. Эта идея, по сути, является наиболее существенной точкой роста для последующих работ. Другой важной точкой роста является развитие концепции доказательства как формального математического объекта.ru
dc.format.mimetypeapplication/pdfru
dc.publisherБГТУru
dc.subjectалгоритмизацияru
dc.subjectалгоритмыru
dc.subjectпрограммированиеru
dc.subjectраспознавание языкаru
dc.subjectполиномиальное времяru
dc.subjectсистема доказательствru
dc.subjectпроблема выполнимостиru
dc.subjectполиномиальная вычислительная сложностьru
dc.subjectфинитность распознавателяru
dc.titleО несоответствии между распознаванием языка за полиномиальное время и тотальной полиномиальностью распознавателяru
dc.typeArticleen
dc.identifier.udc681.142.2-
Appears in Collections:выпуск журнала постатейно

Files in This Item:
File Description SizeFormat 
German_O nesootvetstvii.pdf293.23 kBAdobe PDFView/Open



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.