Please use this identifier to cite or link to this item:
https://elib.belstu.by/handle/123456789/26631
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Герман, Юлия Олеговна | ru |
dc.contributor.author | Герман, Олег Витольдович | ru |
dc.date.accessioned | 2018-11-12T05:30:56Z | - |
dc.date.available | 2018-11-12T05:30:56Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | Герман, Ю. О. О несоответствии между распознаванием языка за полиномиальное время и тотальной полиномиальностью распознавателя / Ю. О. Герман, О. В. Герман // Труды БГТУ. Сер. 3, Физико-математические науки и информатика. - Минск : БГТУ, 2018. - № 2 (212). - С. 119-123. | ru |
dc.identifier.uri | https://elib.belstu.by/handle/123456789/26631 | - |
dc.description.abstract | Приводимые в статье рассуждения устанавливают разницу между тотальной полиномиальностью распознающей машины и полиномиальной сложностью реализуемого ею алгоритма. Проблема связана с отождествлением выводов и доказательств, что не всегда допустимо. Кроме того, нужно иметь в виду, что доказательство становится некорректным, если оно доказывает предикат, являющийся характеристической функцией изменяющегося в процессе доказательства множества. Таким образом, множество доказательств, вообще говоря, не следует отождествлять с множеством корректно построенных выводов. Применительно к теории вычислительной сложности заметим, что трудности доказательства P ≠ NP могут быть напрямую связаны с рассматриваемыми в данной статье проблемами теории доказательств. Возникает идея сведения языка, распознаваемого некоторой детерминированной машиной М за полиномиальное время, при условии, что для М нет доказательства тотальной полиномиальности, к языку Выполнимость. Эта идея, по сути, является наиболее существенной точкой роста для последующих работ. Другой важной точкой роста является развитие концепции доказательства как формального математического объекта. | ru |
dc.format.mimetype | application/pdf | ru |
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.type | Article | en |
dc.identifier.udc | 681.142.2 | - |
Appears in Collections: | выпуск журнала постатейно |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
German_O nesootvetstvii.pdf | 293.23 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.