Kalpana Kalpana (Editor)

Nonelementary problem

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In computational complexity theory, a nonelementary problem is a problem that is not a member of the class ELEMENTARY.

Examples of nonelementary problems that are nevertheless decidable include:

  • the problem of regular expression equivalence with complementation
  • decision problem for monadic second-order logic over trees
  • decision problem for term algebras

    • References

    Nonelementary problem Wikipedia
    (Text) CC BY-SA