Nonelementary problem
Jump to navigation
Jump to search
In computational complexity theory, a nonelementary problem[1] is a problem that is not a member of the class ELEMENTARY. As a class it is sometimes denoted as NONELEMENTARY.
Examples of nonelementary problems that are nevertheless decidable include:
- the problem of regular expression equivalence with complementation[2]
- the decision problem for monadic second-order logic over trees (see S2S)[3]
- the decision problem for term algebras[4]
- satisfiability of W. V. O. Quine's fluted fragment of first-order logic[5]
- deciding β-convertibility of two closed terms in typed lambda calculus[6]
- reachability in vector addition systems; it is Ackermann-complete.[7][8]
- reachability in Petri nets; it is Ackermann-complete.[9][8]
References
<templatestyles src="Reflist/styles.css" />
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1".
- ↑ a b Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
Script error: No such module "Check for unknown parameters".