Quali tipi di proprietà stringa sono verificabili in tempo polinomiale?

Question

Quando viene data la stringa e la proprietà in questione come potenziale certificato. C'è qualche teorema di classificazione che dice qualcosa sulla falsariga di: Tutte le proprietà (di stringhe) che hanno questa proprietà (come una proprietà secondaria) sono verificabili in tempo polinomiale?

Ci sono collezioni di tipi di modelli in stringhe che sono verificabili in Poly Time?

Una proprietà banale è che una raccolta di stringhe con queste proprietà appartiene a una lingua in NP (appartenente a NP è la proprietà secondaria).

Sto cercando qualcosa di più concreto.

Sto cercando il thread comune tra le proprietà stringa come queste che rende queste proprietà verificabili in Poly Time per qualsiasi stringa.

I.e. C'è un modo per scegliere le proprietà delle stringhe da un cappello in modo tale che le proprietà che scelgano siano garantite per essere verificabili in Poly Time in qualsiasi stringa.

Forse c'è un modo per farlo con una complessità implicita - dove le uniche proprietà che puoi costruire (in qualche lingua limitata) sono quelle che sono verificabili in Poly Time?

Answer 1

Verifica di una proprietà di stringhe su un alfabeto $ \ sigma $ è precisamente lo stesso problema di verificare se una stringa è parte di una lingua, chiamata entscheidungsproblem o decisione problema.

Lingua: $ \ Sigma ^ * \ MAPSTO \ {0,1 \} $

Ciò che ti interessa sono "proprietà di stringhe" o in altre parole "classi di lingue".

La classe che probabilmente stai cercando è 'P', che contiene tutte le lingue per le quali il problema decisionale può essere risolto in tempo polinomiale su una macchina di tenuto deterministica. È interessante notare che questa classe è la stessa della classe di lingue per le quali il problema decisionale può essere risolto da circuiti polinomiali.

Tutti i programmi C che contengono passanti costantemente limitati appartengono a P, ad esempio (possono essere facilmente trasformati in un circuito polinomiale). Da lì è possibile estendere la lingua per includere altri anelli che terminano in tempo polinomiale. Devi stare attento con i loop annidati. Ci sono logiche speciali di tipo Hoare per questo scopo.