Welche Arten von String-Eigenschaften sind in der Polynomzeit nachprüfbar?

Question

wenn der String und die betreffende Immobilie als potenzielles Zertifikat angegeben ist. Gibt es ein Klassifizierungs-Theorem, der in den Zeilen etwas sagt: Alle Eigenschaften (von Strings), die diese Eigenschaft (als Untergrundlage) aufweisen, sind in der Polynomzeit nachprüfbar?

Gibt es Kollektionen von Mustern in Strings, die in der Polyzeit überprüfbar sind?

Eine triviale Eigenschaft ist, dass eine Sammlung von Saiten mit diesen Eigenschaften zu einer Sprache in NP gehört (Zugehörigkeit zu NP, die Untereigentum ist).

Ich suche etwas konkreter.

Ich suche nach dem gemeinsamen Thread zwischen den Zeichenfolgeneigenschaften wie diese, die diese Eigenschaften in der Poly-Zeit für jede Zeichenfolge überprüft werden.

d. H. Gibt es einen Weg, um Eigenschaften von Saiten aus einem Hut so auszuwählen, dass die Eigenschaften, die Sie auswählen, garantiert in der Polyzeit in jeder Schnur nachprüfbar sind.

Vielleicht gibt es einen Weg, dies mit impliziten Komplexität zu tun - wo die einzigen Eigenschaften, die Sie bauen können (in einer eingeschränkten Sprache), die in der Polyzeit überprüfbar sind?

Answer 1

Überprüfung einer Eigenschaft von Zeichenfolgen über ein Alphabet $ \ Sigma $ ist genau das gleiche Problem wie das Überprüfen, ob eine Zeichenfolge Teil einer Sprache ist, die als Entwürdigungsproblem oder Entscheidung genannt wird Problem.

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

Was Sie interessieren, sind "Eigenschaften von Saiten" oder mit anderen Worten "Sprachenklassen".

Die Klasse, nach der Sie wahrscheinlich suchen, ist 'P', das alle Sprachen enthält, für die das Entscheidungsproblem in der Polynomialzeit auf einer deterministischen Turingmaschine gelöst werden kann. Interessanterweise ist diese Klasse mit der Klasse der Sprachen, für die das Entscheidungsproblem durch Polynomkreisläufe gelöst werden kann.

Alle C-Programme, die ständig begrenzte Loops enthalten, gehören zum Beispiel (sie können leicht in einen Polynomkreis umgewandelt werden). Von dort aus können Sie die Sprache verlängern, um andere Schlaufen aufzunehmen, die in der Polynomzeit enden. Sie müssen vorsichtig mit verschachtelten Schlaufen sein. Zu diesem Zweck gibt es spezielle Hohe-Logik.