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

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

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

проблема эквивалентности регулярных выражений с дополнением ^[2]
проблема решения для монадической логики второго порядка над деревьями ^[3]
проблема решения для термальных алгебр ^[4]
выполнимость рифленого фрагмента логики первого порядка Куайна ^[5]
определение β-конвертируемости двух замкнутых членов в типизированном лямбда-исчислении ^[6]

Ссылки [ править ]

↑ Воробьев, Сергей; Воронков, Андрей (1998), "Сложность нерекурсивных логических программ с комплексными значениями", Труды семнадцатого симпозиума ACM SIGACT-SIGMOD-SIGART по принципам систем баз данных (PODS '98) , Нью-Йорк, Нью-Йорк, США: ACM, стр. . 244-253, CiteSeerX 10.1.1.39.8822 , DOI : 10.1145 / 275487.275515 , ISBN 978-0-89791-996-8.
^ Стокмейер, Ларри Дж. (1974), Сложность решения проблем в теории автоматов и логике (PDF) , доктор философии. докторская диссертация, Массачусетский технологический институт CS1 maint: обескураженный параметр ( ссылка )
^ Либкин, Леонид (2006), «Логика для деревьев без рейтинга: обзор», Логические методы в компьютерных науках , 2 (3): 3: 2, 31, arXiv : cs.LO / 0606062 , doi : 10.2168 / LMCS-2 (3: 2) 2006 , MR 2295773 .
↑ Воробьев, Сергей (1996), "Улучшенная нижняя оценка для элементарных теорий деревьев", Автоматизированный вывод - CADE-13: 13-я Международная конференция по автоматическому выводу Нью-Брансуик, Нью-Джерси, США, 30 июля - 3 августа 1996 г., Труды , Lecture Notes в области компьютерных наук, 1104 ., Springer, С. 275-287, CiteSeerX 10.1.1.39.1499 , DOI : 10.1007 / 3-540-61511-3_91 , ISBN 978-3-540-61511-8.
^ Пратт-Хартманн, Ян; Шваст, Веслав; Тендера, Лидия (2016), «Рифленый фрагмент Куайна неэлементарен», в Talbot, Jean-Marc; Ренье, Лоран (ред.), 25-я Ежегодная конференция EACSL по компьютерной логике, CSL 2016, 29 августа - 1 сентября 2016 г., Марсель, Франция , LIPIcs, 62 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 39: 1 -39: 21, DOI : 10,4230 / LIPIcs.CSL.2016.39
^ Статман, Ричард (1979), «Типизированное λ-исчисление не является элементарно рекурсивным», Теоретическая информатика , 9 : 73–81, DOI : 10.1016 / 0304-3975 (79) 90007-0 , hdl : 2027.42 / 23535.

P ≟ NP

Эта статья по теоретической информатике незавершена . Вы можете помочь Википедии, расширив ее .

[1] Воробьев, Сергей; Воронков, Андрей (1998), "Сложность нерекурсивных логических программ с комплексными значениями", Труды семнадцатого симпозиума ACM SIGACT-SIGMOD-SIGART по принципам систем баз данных (PODS '98) , Нью-Йорк, Нью-Йорк, США: ACM, стр. . 244-253, CiteSeerX 10.1.1.39.8822 , DOI : 10.1145 / 275487.275515 , ISBN 978-0-89791-996-8.

[2] Стокмейер, Ларри Дж. (1974), Сложность решения проблем в теории автоматов и логике (PDF) , доктор философии. докторская диссертация, Массачусетский технологический институт CS1 maint: обескураженный параметр ( ссылка )

[3] Либкин, Леонид (2006), «Логика для деревьев без рейтинга: обзор», Логические методы в компьютерных науках , 2 (3): 3: 2, 31, arXiv : cs.LO / 0606062 , doi : 10.2168 / LMCS-2 (3: 2) 2006 , MR 2295773 .

[4] Воробьев, Сергей (1996), "Улучшенная нижняя оценка для элементарных теорий деревьев", Автоматизированный вывод - CADE-13: 13-я Международная конференция по автоматическому выводу Нью-Брансуик, Нью-Джерси, США, 30 июля - 3 августа 1996 г., Труды , Lecture Notes в области компьютерных наук, 1104 ., Springer, С. 275-287, CiteSeerX 10.1.1.39.1499 , DOI : 10.1007 / 3-540-61511-3_91 , ISBN 978-3-540-61511-8.

[5] Пратт-Хартманн, Ян; Шваст, Веслав; Тендера, Лидия (2016), «Рифленый фрагмент Куайна неэлементарен», в Talbot, Jean-Marc; Ренье, Лоран (ред.), 25-я Ежегодная конференция EACSL по компьютерной логике, CSL 2016, 29 августа - 1 сентября 2016 г., Марсель, Франция , LIPIcs, 62 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 39: 1 -39: 21, DOI : 10,4230 / LIPIcs.CSL.2016.39

[6] Статман, Ричард (1979), «Типизированное λ-исчисление не является элементарно рекурсивным», Теоретическая информатика , 9 : 73–81, DOI : 10.1016 / 0304-3975 (79) 90007-0 , hdl : 2027.42 / 23535.

[1]