0
$\begingroup$

When given the string and the property in question as a potential certificate. Is there any classification theorem that says something along the lines of: all properties (of strings) that have this property (as a sub property) are verifiable in polynomial time?

Are there any collections of types of patterns in strings that are verifiable in poly time?

A trivial property is that a collection of strings with these properties belong to a language in NP (belonging to NP being the sub property).

I'm looking for something more concrete.

I'm looking for the common thread between string properties like these that makes these properties verifiable in poly time for any string.

i.e. is there a way to pick properties of strings out of a hat in such a way that the properties you pick are guaranteed to be verifiable in poly time in any string.

Maybe there is a way to do this with implicit complexity--where the only properties you can build (in some restricted language) are the ones that are verifiable in poly time?

$\endgroup$
4
$\begingroup$

Verifying a property of strings over an alphabet $\Sigma$ is precisely the same problem as checking whether a string is part of a language, called the Entscheidungsproblem or decision problem.

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

What you are interested in are 'properties of strings' or in other words 'classes of languages'.

The class you are probably looking for is 'P', which contains all languages for which the decision problem can be solved in polynomial time on a deterministic Turing machine. Interestingly this class is the same as the class of languages for which the decision problem can be solved by polynomial circuits.

All C programs which contain constantly bounded loops belong to P for example (they can easily be turned into a polynomial circuit). From there you can extend the language to include other loops that terminate in polynomial time. You have to be careful with nested loops. There are special Hoare-type logics for this purpose.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks! my question was poorly worded. Are there any common techniques to guarantee that a class of languages (you are trying to build/ specify) are polynomially decidable? like, what are some porperties that if these strings had them this would guarantee that this language consisting of strings with these properties was decidable in poly time? $\endgroup$ – DeeDee Apr 21 at 21:07
  • $\begingroup$ @RingRing, that's called (more or less) "complexity theory". Determining conditions on whether a language is in P or not is at the center of the most famous open problem in all of computer science, P vs NP. $\endgroup$ – vonbrand Apr 21 at 21:52
  • $\begingroup$ @RingRing, one such property is whether the language of those strings is context-free. If a language is context-free, then its membership problem is polynomially decidable. $\endgroup$ – John L. Apr 21 at 23:51
  • $\begingroup$ @JohnL. Ya, I'm looking for a list of properties like this. I know that there are still many mysteries but I also know a lot of results have been proven and there are likely 100's of properties that if your language has them confirm you are polynomially decidable. Is there any repository of these properties? $\endgroup$ – DeeDee Apr 23 at 16:43
  • $\begingroup$ @vonbrand like In my comment above, I guess what I'm looking for is a list of language properties we know of that confirm you are a member of P. How long of a list does humanity have at this point? $\endgroup$ – DeeDee Apr 23 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.