Nonelementary problem
id:
nonelementary-problem-319-15201083
title:
Nonelementary problem
text:
In computational complexity theory, a nonelementary problem 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
the decision problem for monadic second-order logic over trees
the decision problem for term algebras
satisfiability of W. V. O. Quine's fluted fragment of first-order logic
deciding β-
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Nonelementary_problem
date created:
date modified:
2024-01-28T05:05:16Z
main entity:
{"identifier":"Q6954914","url":"https://www.wikidata.org/entity/Q6954914"}
image:
fields total:
13
integrity:
13