Неэлементарная задача

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

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

проблема эквивалентности регулярных выражений с дополнением ^[2]
проблема решения для монадической логики второго порядка над деревьями (см. S2S ) ^[3]
проблема решения для термальных алгебр ^[4]
выполнимость WVO Куайна рифленого фрагмента логики первого порядка ^[5]
определение β-конвертируемости двух замкнутых термов в типизированном лямбда-исчислении ^[6]
достижимость в системах сложения векторов ; оно аккерманово -полно. ^[7]^[8]
достижимость в сетях Петри ; оно аккерманово -полно. ^[9]^[8]

Ссылки

^ Воробьев Сергей; Воронков, Андрей (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 , S2CID 15631793 .
^ Стокмейер, Ларри Дж. (1974), Сложность проблем принятия решений в теории автоматов и логике (PDF) , доктор философии. диссертация, Массачусетский технологический институт
^ Либкин, Леонид (2006), «Логика для неранжированных деревьев: обзор», Логические методы в информатике , 2 (3): 3:2, 31, arXiv : cs.LO/0606062 , doi : 10.2168/LMCS-2( 3:2) 2006 , МР 2295773 .
^ Воробьев, Сергей (1996), «Улучшенная нижняя граница для элементарных теорий деревьев», Автоматический вывод - CADE-13: 13-я Международная конференция по автоматическому выводу, Нью-Брансуик, Нью-Джерси, США, 30 июля – 3 августа 1996 г., Труды , Конспекты лекций по информатике, том. 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), «Фрагмент с каннелюрами Куайна неэлементарен», у Талбота, Жан-Марка; Ренье, Лоран (ред.), 25-я ежегодная конференция EACSL по логике компьютерных наук, CSL 2016, 29 августа – 1 сентября 2016 г., Марсель, Франция , LIPIcs, vol. 62, Schloss Dagstuhl – Центр компьютерных наук Лейбница, стр. 39:1–39:21, doi : 10.4230/LIPIcs.CSL.2016.39
^ Статман, Ричард (1979), «Типизированное λ-исчисление не является элементарно-рекурсивным», Theoretical Computer Science , 9 : 73–81, doi : 10.1016/0304-3975(79)90007-0 , hdl : 2027.42/23535 .
^ Червинский, Войцех; Орликовский, Лукаш (2021). Достижимость в системах сложения векторов является полной по Аккерману . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS), 2021 г. arXiv : 2104.13866 .
^ Jump up to: Перейти обратно: ^а ^б Брубейкер, Бен (4 декабря 2023 г.). «Просто кажущаяся проблема дает числа, слишком большие для нашей Вселенной» . Журнал Кванта .
^ Леру, Жером (февраль 2022 г.). «Проблема достижимости сетей Петри не является примитивно-рекурсивной» . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2021 г. IEEE. стр. 1241–1252. arXiv : 2104.12695 . дои : 10.1109/FOCS52979.2021.00121 . ISBN 978-1-6654-2055-6 .

П ≟ НП

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

[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 , S2CID 15631793 .

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

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

[4] Воробьев, Сергей (1996), «Улучшенная нижняя граница для элементарных теорий деревьев», Автоматический вывод - CADE-13: 13-я Международная конференция по автоматическому выводу, Нью-Брансуик, Нью-Джерси, США, 30 июля – 3 августа 1996 г., Труды , Конспекты лекций по информатике, том. 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), «Фрагмент с каннелюрами Куайна неэлементарен», у Талбота, Жан-Марка; Ренье, Лоран (ред.), 25-я ежегодная конференция EACSL по логике компьютерных наук, CSL 2016, 29 августа – 1 сентября 2016 г., Марсель, Франция , LIPIcs, vol. 62, Schloss Dagstuhl – Центр компьютерных наук Лейбница, стр. 39:1–39:21, doi : 10.4230/LIPIcs.CSL.2016.39

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

[7] Червинский, Войцех; Орликовский, Лукаш (2021). Достижимость в системах сложения векторов является полной по Аккерману . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS), 2021 г. arXiv : 2104.13866 .

[:0-8] Jump up to: Перейти обратно: ^а ^б Брубейкер, Бен (4 декабря 2023 г.). «Просто кажущаяся проблема дает числа, слишком большие для нашей Вселенной» . Журнал Кванта .

[9] Леру, Жером (февраль 2022 г.). «Проблема достижимости сетей Петри не является примитивно-рекурсивной» . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2021 г. IEEE. стр. 1241–1252. arXiv : 2104.12695 . дои : 10.1109/FOCS52979.2021.00121 . ISBN 978-1-6654-2055-6 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]