Quels types de propriétés de chaîne sont vérifiables en temps polynomial?

Question

Lorsque vous émettez la chaîne et la propriété en question comme un certificat potentiel. Y a-t-il un théorème de classification qui dit quelque chose dans le sens de: toutes les propriétés (des chaînes) qui ont cette propriété (comme une sous-propriété) sont vérifiables en temps polynomial?

Y a-t-il des collections de types de motifs dans les chaînes vérifiables en poly time?

Une propriété triviale est qu'une collection de chaînes avec ces propriétés appartiennent à une langue dans NP (appartenant à NP étant la sous-propriété).

Je cherche quelque chose de plus concret.

Je cherche le fil commun entre les propriétés de chaîne comme ceux-ci qui rend ces propriétés vérifiables en poly time pour n'importe quelle chaîne.

I.e. Existe-t-il un moyen de choisir des propriétés des chaînes d'un chapeau de manière à ce que les propriétés que vous choisissez soient garanties de manière vérifiable en poly time dans n'importe quelle chaîne.

Peut-être qu'il y a un moyen de le faire avec une complexité implicite - où les seules propriétés que vous pouvez construire (dans certaines langues restreintes) sont celles qui sont vérifiables en poly time?

Answer 1

Vérification d'une propriété de chaînes sur un alphabet $ \ sigma $ est précisément le même problème que de vérifier si une chaîne fait partie d'une langue, appelée tscheidungsproblème ou décision problème.

Langue: $ \ SIGMA ^ * \ MAPSTO \ {0,1 \} $

Ce que vous êtes intéressé est «Propriétés des chaînes» ou, en d'autres termes, «Classes de langues».

La classe que vous recherchez probablement est 'P', qui contient toutes les langues pour lesquelles le problème de décision peut être résolu en temps polynomial sur une machine à trouble déterministe. Fait intéressant, cette classe est la même que la classe de langues pour laquelle le problème de décision peut être résolu par des circuits polynomiaux.

Tous les programmes C contenant des boucles constamment liées appartiennent à P par exemple (ils peuvent facilement être transformés en circuit polynomial). De là, vous pouvez étendre la langue à inclure d'autres boucles qui se terminent en temps polynomial. Vous devez faire attention avec des boucles imbriquées. Il existe des logiques de type hoare spéciales à cette fin.