Неэлементарная проблема - Nonelementary problem

В теория сложности вычислений, а неэлементарная проблема[1] это проблема, которая не входит в класс НАЧАЛЬНЫЙ. Как класс он иногда обозначается как НЕЭЛЕМЕНТАРНЫЙ.

Примеры неэлементарных проблем, которые, тем не менее, разрешимы, включают:

Рекомендации

  1. ^ Воробьев, Сергей; Воронков, Андри (1998), "Сложность нерекурсивных логических программ с комплексными значениями", Материалы семнадцатого симпозиума ACM SIGACT-SIGMOD-SIGART по принципам систем баз данных (PODS '98), Нью-Йорк, Нью-Йорк, США: ACM, стр. 244–253, CiteSeerX  10.1.1.39.8822, Дои:10.1145/275487.275515, ISBN  978-0-89791-996-8.
  2. ^ Стокмейер, Ларри Дж. (1974), Сложность решения задач в теории и логике автоматов (PDF), Кандидат наук. докторская диссертация, Массачусетский технологический институт
  3. ^ Либкин, Леонид (2006), "Логика для деревьев без рейтинга: обзор", Логические методы в информатике, 2 (3): 3:2, 31, arXiv:cs.LO / 0606062, Дои:10.2168 / LMCS-2 (3: 2) 2006 г., МИСТЕР  2295773.
  4. ^ Воробьев, Сергей (1996), "Улучшенная нижняя оценка элементарных теорий деревьев", Automated Deduction - Cade-13: 13-я Международная конференция по автоматизированному вычету Нью-Брансуик, Нью-Джерси, США, 30 июля - 3 августа 1996 г., Труды, Конспект лекций по информатике, 1104, Springer, стр. 275–287, CiteSeerX  10.1.1.39.1499, Дои:10.1007/3-540-61511-3_91, ISBN  978-3-540-61511-8.
  5. ^ "Рифленый фрагмент Куайна не является элементарным" (PDF).