Nonelementary problem

From Wikipedia, the free encyclopedia
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.

Examples of nonelementary problems that are nevertheless decidable include:


  1. ^ Vorobyov, Sergei; Voronkov, Andrie (1998), "Complexity of Nonrecursive Logic Programs with Complex Values", Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '98), New York, NY, USA: ACM, pp. 244–253, doi:10.1145/275487.275515, ISBN 0-89791-996-3 .
  2. ^ Stockmeyer, Larry J. (1974), The Complexity of Decision Problems in Automata Theory and Logic (PDF), Ph.D. dissertation, Massachusetts Institute of Technology 
  3. ^ Libkin, Leonid (2006), "Logics for unranked trees: an overview", Logical Methods in Computer Science, 2 (3): 3:2, 31, arXiv:cs.LO/0606062Freely accessible, doi:10.2168/LMCS-2(3:2)2006, MR 2295773 .
  4. ^ Vorobyov, Sergei (1996), "An improved lower bound for the elementary theories of trees", Automated Deduction — Cade-13: 13th International Conference on Automated Deduction New Brunswick, NJ, USA, July 30 – August 3, 1996, Proceedings, Lecture Notes in Computer Science, 1104, Springer, pp. 275–287, doi:10.1007/3-540-61511-3_91 .
  5. ^ "Quine's Fluted Fragment is Non-Elementary" (PDF).