I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata that can implement the algorithm. For example is there a range of complexity push down automata can express? If the answer is yes to said question is there a resource depicting the relationship? Thanks!
Asked By : Harpo Roeder
Answered By : jmite
Yes, there are relationships in many cases!
For example, it is known that any language which is accepted by reversal-bounded counter machines are in $P$ (see here).
Similarly, we know that all regular languages are in $P$, since there's a polynomial time algorithm for determining if an NFA accepts a given word.
There are too many to enumerate here, but in general, more limited computation models are in easier complexity classes.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/52748
0 comments:
Post a Comment
Let us know your responses and feedback