Que tipos de propriedades de seqüência de caracteres são verificáveis em tempo polinomial?

Question

Quando dada a seqüência e a propriedade em questão como um potencial de certificado.Existe alguma classificação teorema que diz algo ao longo das linhas de:todas as propriedades (de cordas) que têm esta propriedade (como uma sub-propriedade) são verificáveis em tempo polinomial?

Existem coleções de tipos de padrões em seqüências de caracteres que são verificáveis na poli tempo?

Uma propriedade trivial é que um conjunto de cadeias de caracteres com essas propriedades pertencem a uma linguagem em NP (pertencente a NP sendo a sub-propriedade).

Eu estou procurando algo mais concreto.

Eu estou olhando para a linha comum entre propriedades de seqüência de caracteres como esses que faz com que essas propriedades verificáveis na poli tempo para qualquer seqüência de caracteres.

i.e.existe uma maneira para escolher as propriedades das cordas de um chapéu de tal forma que as propriedades que você escolher são garantidos para ser verificável na poli tempo, em qualquer seqüência de caracteres.

Talvez haja uma maneira de fazer isso com a complexidade implícita--onde apenas as propriedades que você pode construir (em alguns restritos língua) são aqueles que são verificáveis na poli tempo?

Answer 1

Verificando uma propriedade de cadeias de mais de um alfabeto $\Sigma$ é precisamente o mesmo problema como verificar se uma string é parte de uma linguagem, chamada o Entscheidungsproblem ou problema de decisão.

Idioma : $\Sigma^* \mapsto \{0,1\}$

O que você está interessado em são propriedades de seqüências de caracteres "ou em outras palavras, "aulas de idiomas'.

A classe que você está procurando provavelmente é "P", que contém todos os idiomas para os quais o problema de decisão pode ser resolvido em tempo polinomial em uma máquina de Turing determinística.Curiosamente, esta classe é o mesmo que a classe de linguagens para que o problema de decisão pode ser resolvido pelo polinômio de circuitos.

Todos os programas em C que contêm constantemente limitado loops pertencem a P, por exemplo (que pode ser facilmente transformado em um polinˆ omio de circuito).De lá, você pode estender a linguagem para incluir outros ciclos que terminam em tempo polinomial.Você tem que ter cuidado com loops aninhados.Existem especial Hoare-tipo de lógica para esta finalidade.