多项式时间可验证哪些类型的字符串属性？

Question

当赋予字符串和属性作为潜在证书时。是否有任何分类定理，这些定理表明沿着：具有此属性的所有属性（字符串）（作为子属性）在多项式时间内可验证？

在多时间内可核实的字符串中有任何类型的图案类型吗？

琐碎的属性是具有这些属性的字符串集合属于np中的语言（属于np是子属性）。

我正在寻找更具体的东西。

我正在寻找字符串属性之间的通用线程，如这些属性，使得这些属性在任何字符串中验证这些属性。

i.e。是否有一种方法可以以这样的方式选择帽子的属性，使您选择的属性保证在任何字符串中的多时间中可验证。

也许有一种方法可以通过隐式复杂性执行此操作 - 其中您可以构建的唯一属性（以某种限制语言）是在多时间核算中可验证的属性？

Answer 1

通过字母 $ \ sigma $ 验证字符串的属性与检查字符串是否是语言的一部分，称为OntscheidungsProblus或决定相同的问题问题。

语言： $ \ sigma ^ * \ mapsto \ {0,1 \} $

您感兴趣的是'字符串属性'或换句话说'语言类别'。

您可能正在寻找的课程是'p'，其中包含所有语言，在确定性图灵机上的多项式时间中可以解决决策问题。有趣的是这个课程与多项式电路可以解决决策问题的语言相同。

包含不断有界循环的所有C程序属于P，例如（它们很容易变成多项式电路）。 从那里，您可以扩展语言以包括终止多项式时间的其他循环。你必须小心嵌套环。为此目的有特殊的Hoare型逻辑。