Какие типы строковых свойств поддаются проверке за полиномиальное время?
-
29-09-2020 - |
Вопрос
Когда задается строка и рассматриваемое свойство в качестве потенциального сертификата.Существует ли какая-либо классификационная теорема, которая говорит что-то вроде:все свойства (строк), которые обладают этим свойством (как вложенным свойством), проверяемы за полиномиальное время?
Существуют ли какие-либо коллекции типов шаблонов в строках, которые поддаются проверке в поли-времени?
Тривиальным свойством является то, что набор строк с этими свойствами принадлежит языку в NP (принадлежность к NP является вложенным свойством).
Я ищу что-то более конкретное.
Я ищу общую нить между строковыми свойствами, подобными этим, которая делает эти свойства проверяемыми в поли-времени для любой строки.
т. е.есть ли способ выбрать свойства строк из шляпы таким образом, чтобы выбранные вами свойства гарантированно были проверяемы в поли-времени в любой строке?
Может быть, есть способ сделать это с неявной сложностью - где единственными свойствами, которые вы можете создать (на каком-то ограниченном языке), являются те, которые можно проверить в поли-времени?
Решение
Проверка свойства строк по алфавиту $\Сигма$ это точно такая же проблема, как проверка того, является ли строка частью языка, называемая Entscheidungsproblem или проблемой принятия решения.
Язык : $\Сигма^* \mapsto \{0,1\}$
То, что вас интересует, - это "свойства строк" или, другими словами, "классы языков".
Класс, который вы, вероятно, ищете, - это "P", который содержит все языки, для которых задача принятия решения может быть решена за полиномиальное время на детерминированной машине Тьюринга.Интересно, что этот класс совпадает с классом языков, для которых задача принятия решения может быть решена с помощью полиномиальных схем.
Например, все программы на языке Си, содержащие постоянно ограниченные циклы, принадлежат P (их можно легко превратить в полиномиальную схему).Оттуда вы можете расширить язык, включив в него другие циклы, которые заканчиваются за полиномиальное время.Вы должны быть осторожны с вложенными циклами.Для этой цели существуют специальные логики типа Хоара.