О несоответствии между распознаванием языка за полиномиальное время и тотальной полиномиальностью распознавателя

Abstract

Приводимые в статье рассуждения устанавливают разницу между тотальной полиномиальностью распознающей машины и полиномиальной сложностью реализуемого ею алгоритма. Проблема связана с отождествлением выводов и доказательств, что не всегда допустимо. Кроме того, нужно иметь в виду, что доказательство становится некорректным, если оно доказывает предикат, являющийся характеристической функцией изменяющегося в процессе доказательства множества. Таким образом, множество доказательств, вообще говоря, не следует отождествлять с множеством корректно построенных выводов. Применительно к теории вычислительной сложности заметим, что трудности доказательства P ≠ NP могут быть напрямую связаны с рассматриваемыми в данной статье проблемами теории доказательств. Возникает идея сведения языка, распознаваемого некоторой детерминированной машиной М за полиномиальное время, при условии, что для М нет доказательства тотальной полиномиальности, к языку Выполнимость. Эта идея, по сути, является наиболее существенной точкой роста для последующих работ. Другой важной точкой роста является развитие концепции доказательства как формального математического объекта.