¿Qué tipos de propiedades de cadena son verificables en el tiempo polinomial?

Question

Cuando se le da la cadena y la propiedad en cuestión como un certificado potencial. ¿Hay algún teorema de la clasificación que dice algo a lo largo de las líneas de: todas las propiedades (de cadenas) que tienen esta propiedad (como una propiedad secundaria) son verificables en el tiempo polinomial?

¿Hay alguna colección de tipos de patrones en cadenas que sean verificables en polietileno?

Una propiedad trivial es que una colección de cuerdas con estas propiedades pertenece a un idioma en NP (perteneciente a NP es la propiedad secundaria).

Estoy buscando algo más concreto.

Estoy buscando el hilo común entre las propiedades de cadena como estas que hacen que estas propiedades sea verificables en tiempo de polietileno para cualquier cadena.

es. ¿Hay una manera de elegir las propiedades de las cuerdas de un sombrero de tal manera que las propiedades que seleccione se garanticen para ser verificables en el tiempo de polietileno en cualquier cadena?

Tal vez hay una manera de hacerlo con complejidad implícita: ¿dónde las únicas propiedades que puede construir (en algún idioma restringido) son las que son verificables en polietileno?

Answer 1

Verificación de una propiedad de cadenas sobre un alfabeto $ \ sigma $ es precisamente el mismo problema que verificando si una cadena es parte de un idioma, llamado intscheidungsproblem o decisión problema.

Idioma: $ \ sigma ^ * \ mapsto \ {0,1}} \ {span>

Lo que le interesa son 'propiedades de las cadenas' o en otras palabras 'Clases de lenguas'.

La clase que probablemente está buscando es 'P', que contiene todos los idiomas para los cuales el problema de la decisión se puede resolver en el tiempo polinomial en una máquina de Turing determinista. Curiosamente, esta clase es la misma que la clase de idiomas para las cuales el problema de la decisión puede resolverse con circuitos polinomiales.

Todos los programas C que contienen bucles constantemente limitados pertenecen a P, por ejemplo, (se pueden convertir fácilmente en un circuito polinomial). Desde allí, puede extender el idioma para incluir otros bucles que terminan en tiempo polinomial. Tienes que tener cuidado con los bucles anidados. Hay lógicas especiales de tipo Hoare para este propósito.