Какие типы строковых свойств поддаются проверке за полиномиальное время?

Question

Когда задается строка и рассматриваемое свойство в качестве потенциального сертификата.Существует ли какая-либо классификационная теорема, которая говорит что-то вроде:все свойства (строк), которые обладают этим свойством (как вложенным свойством), проверяемы за полиномиальное время?

Существуют ли какие-либо коллекции типов шаблонов в строках, которые поддаются проверке в поли-времени?

Тривиальным свойством является то, что набор строк с этими свойствами принадлежит языку в NP (принадлежность к NP является вложенным свойством).

Я ищу что-то более конкретное.

Я ищу общую нить между строковыми свойствами, подобными этим, которая делает эти свойства проверяемыми в поли-времени для любой строки.

т. е.есть ли способ выбрать свойства строк из шляпы таким образом, чтобы выбранные вами свойства гарантированно были проверяемы в поли-времени в любой строке?

Может быть, есть способ сделать это с неявной сложностью - где единственными свойствами, которые вы можете создать (на каком-то ограниченном языке), являются те, которые можно проверить в поли-времени?

Answer 1

Проверка свойства строк по алфавиту $\Сигма$ это точно такая же проблема, как проверка того, является ли строка частью языка, называемая Entscheidungsproblem или проблемой принятия решения.

Язык : $\Сигма^* \mapsto \{0,1\}$

То, что вас интересует, - это "свойства строк" или, другими словами, "классы языков".

Класс, который вы, вероятно, ищете, - это "P", который содержит все языки, для которых задача принятия решения может быть решена за полиномиальное время на детерминированной машине Тьюринга.Интересно, что этот класс совпадает с классом языков, для которых задача принятия решения может быть решена с помощью полиномиальных схем.

Например, все программы на языке Си, содержащие постоянно ограниченные циклы, принадлежат P (их можно легко превратить в полиномиальную схему).Оттуда вы можете расширить язык, включив в него другие циклы, которые заканчиваются за полиномиальное время.Вы должны быть осторожны с вложенными циклами.Для этой цели существуют специальные логики типа Хоара.