Список неразрешимых проблем
Вычислительные задачи, которые не может решить ни один алгоритм

В теории вычислимости неразрешимая проблема — это проблема принятия решений , для которой не существует эффективного метода (алгоритма) для получения правильного ответа. Более формально, неразрешимая проблема — это проблема, язык которой не является рекурсивным множеством ; см. статью Разрешимый язык . Существует несчетное количество неразрешимых проблем, поэтому приведенный ниже список обязательно неполный. Хотя неразрешимые языки не являются рекурсивными языками, они могут быть подмножествами распознаваемых по Тьюрингу языков: т. е. такие неразрешимые языки могут быть рекурсивно перечислимыми.

Многие, если не большинство, неразрешимых проблем в математике можно сформулировать как текстовые задачи : определить, когда две различные строки символов (кодирующие некоторое математическое понятие или объект) представляют один и тот же объект, а когда нет.

О неразрешимости в аксиоматической математике см. Список утверждений, неразрешимых в ZFC .

Проблемы с логикой

Проблемы с абстрактными машинами

  • Проблема остановки (определение того, останавливается ли машина Тьюринга при заданном входе) и проблема смертности (определение того, останавливается ли она при каждой начальной конфигурации).
  • Определение того, является ли машина Тьюринга чемпионом по трудолюбию (т.е. является ли она самой долго работающей среди останавливающихся машин Тьюринга с тем же количеством состояний и символов).
  • Теорема Райса утверждает, что для всех нетривиальных свойств частичных функций невозможно решить, вычисляет ли данная машина частичную функцию с этим свойством.
  • Проблема остановки регистровой машины : конечный автомат без входов и двумя счетчиками, которые можно увеличивать, уменьшать и проверять на равенство нулю.
  • Универсальность недетерминированного магазинного автомата : определение того, все ли слова приняты.
  • Проблема в том, что система тегов останавливается.

Задачи о матрицах

Задачи по комбинаторной теории групп

Проблемы топологии

Проблемы в анализе

  • Для функций в некоторых классах проблема определения: равны ли две функции, известная как проблема нулевой эквивалентности (см. теорему Ричардсона ); [4] нулей функции; принадлежит ли неопределенный интеграл функции также классу. [5] Конечно, некоторые подклассы этих проблем разрешимы. Например, существует эффективная процедура решения для элементарного интегрирования любой функции, которая принадлежит полю трансцендентных элементарных функций, алгоритм Риша .
  • «Проблема решения вопроса о том, равен ли нулю определенный контурный кратный интеграл элементарной мероморфной функции на всюду действительном аналитическом многообразии, на котором он аналитичен», следствие теоремы MRDP, разрешающей десятую проблему Гильберта . [5]
  • Определение области решения обыкновенного дифференциального уравнения вида
г х г т = п ( т , х ) ,   х ( т 0 ) = х 0 , {\displaystyle {\frac {dx}{dt}}=p(t,x),~x(t_{0})=x_{0},}
где x — вектор в Rn , p ( t , x ) — вектор полиномов от t и x , а ( t0 , x0 ) принадлежит Rn + 1 . [6]

Проблемы с формальными языками и грамматиками

  • Проблема почтовой корреспонденции .
  • Определение того, генерирует ли контекстно-свободная грамматика все возможные строки или она является неоднозначной .
  • Даны две контекстно-свободные грамматики, и определяется, генерируют ли они один и тот же набор строк, или одна из них генерирует подмножество строк, сгенерированных другой, или существует ли вообще какая-либо строка, которую генерируют обе.

Другие проблемы

  • Задача определения, можно ли заданным набором плиток Вана замостить плоскость.
  • Задача определения колмогоровской сложности строки.
  • Десятая проблема Гильберта : проблема определения, имеет ли диофантово уравнение (многомерное полиномиальное уравнение) решение в целых числах.
  • Определение того, является ли заданная начальная точка с рациональными координатами периодической, или лежит ли она в области притяжения заданного открытого множества, в кусочно-линейном итеративном отображении в двух измерениях, или в кусочно-линейном потоке в трех измерениях. [7]
  • Определение того, имеет ли формула λ-исчисления нормальную форму.
  • Игра Конвея «Жизнь» о том, может ли последний рисунок появиться из исходного, если заданы начальный рисунок и другой рисунок.
  • Правило 110 — большинство вопросов, связанных с «может ли свойство X появиться позже», неразрешимы.
  • Проблема определения наличия спектральной щели в квантово-механической системе . [8] [9]
  • Нахождение пропускной способности информационно-устойчивого конечно-автоматного канала. [10]
  • В сетевом кодировании определение того, является ли сеть разрешимой. [11] [12]
  • Определение того, есть ли у игрока выигрышная стратегия в игре Magic: The Gathering . [13]
  • Планирование в частично наблюдаемом марковском процессе принятия решений .
  • Проблема планирования авиаперелетов из одного пункта назначения в другой с учетом стоимости билетов . [14]
  • В задаче трассировки лучей для трехмерной системы отражающих или преломляющих объектов определяется, достигает ли луч, начинающийся в заданном положении и направлении, в конечном итоге определенной точки. [15]
  • Определение того, достигает ли траектория частицы идеальной жидкости в трехмерной области в конечном итоге определенной области в пространстве. [16] [17]

Смотрите также

Примечания

  1. ^ Уэллс, Дж. Б. (1993). «Типичность и проверка типов в лямбда-исчислении второго порядка эквивалентны и неразрешимы». Tech. Rep. 93-011 . Comput. Sci. Dept., Boston Univ.: 176–185. CiteSeerX  10.1.1.31.3590 .
  2. ^ Трахтенброт, Б. А. (1950). «Невозможность алгоритма для задачи принятия решения для конечных областей». Доклады Академии наук СССР . Новая серия. 70 : 569–572. MR  0033784.
  3. ^ Стиллвелл, Джон (1993), Классическая топология и комбинаторная теория групп, Graduate Texts in Mathematics, т. 72, Springer, стр. 247, ISBN 9780387979700.
  4. ^ Кит О. Геддес, Стивен Р. Цапор, Джордж Лабан, Алгоритмы компьютерной алгебры , ISBN 0585332479 , 2007, стр. 81 и далее 
  5. ^ ab Stallworth, Daniel T.; Roush, Fred W. (июль 1997 г.). «Неразрешимое свойство определенных интегралов». Труды Американского математического общества . 125 (7): 2147–2148. doi : 10.1090/S0002-9939-97-03822-7 .
  6. ^ Граса, Даниэль С.; Буэску, Хорхе; Кампаньоло, Мануэль Л. (21 марта 2008 г.). «Ограниченность области определения неразрешима для полиномиальных ОДУ». Электронные заметки по теоретической информатике . 202 : 49–57. doi : 10.1016/j.entcs.2008.03.007 . hdl : 10400.1/1016 .
  7. ^ Мур, Кристофер (1990), «Непредсказуемость и неразрешимость в динамических системах» (PDF) , Physical Review Letters , 64 (20): 2354–2357, Bibcode : 1990PhRvL..64.2354M, doi : 10.1103/PhysRevLett.64.2354, PMID  10041691.
  8. ^ Cubitt, Toby S.; Perez-Garcia, David; Wolf, Michael M. (2015). «Неразрешимость спектральной щели». Nature . 528 (7581): 207–211. arXiv : 1502.04135 . Bibcode :2015Natur.528..207C. doi :10.1038/nature16059. PMID  26659181. S2CID  4451987.
  9. ^ Bausch, Johannes; Cubitt, Toby S.; Lucia, Angelo; Perez-Garcia, David (17 августа 2020 г.). «Неразрешимость спектральной щели в одном измерении». Physical Review X. 10 ( 3): 031038. arXiv : 1810.01858 . Bibcode : 2020PhRvX..10c1038B. doi : 10.1103/PhysRevX.10.031038 .
  10. ^ Элкусс, Д.; Перес-Гарсия, Д. (2018). «Эффекты памяти могут сделать пропускную способность канала связи невычислимой». Nature Communications . 9 (1): 1149. Bibcode :2018NatCo...9.1149E. doi :10.1038/s41467-018-03428-0. PMC 5861076 . PMID  29559615. 
  11. ^ Ли, CT (2023). «Неразрешимость сетевого кодирования, условные информационные неравенства и условная независимость следствия». Труды IEEE по теории информации . 69 (6): 1. arXiv : 2205.11461 . doi : 10.1109/TIT.2023.3247570. S2CID  248986512.
  12. ^ Кюне, Л.; Яшфе, Г. (2022). «Представимость матроидов с помощью c-расположений неразрешима». Israel Journal of Mathematics . 252 : 1-53. arXiv : 1912.06123 . doi : 10.1007/s11856-022-2345-z. S2CID  209324252.
  13. ^ Херрик, Остин; Бидерман, Стелла; Черчилль, Алекс (2019-03-24). «Magic: The Gathering is Turing Complete». arXiv : 1904.09828v2 [cs.AI].
  14. ^ де Маркен, Карл. "Вычислительная сложность планирования авиаперелетов" (PDF) . Программное обеспечение ITA . Получено 4 января 2021 г. .
  15. ^ "Вычислимость и сложность трассировки лучей" (PDF) . CS.Duke.edu .
  16. ^ Кардона, Р.; Миранда, Э.; Перальта-Салас, Д.; Пресас, Ф. (2021). «Построение полных по Тьюрингу потоков Эйлера в размерности 3». Труды Национальной академии наук . 118 (19): 19. arXiv : 2012.12828 . Bibcode : 2021PNAS..11826818C. doi : 10.1073/pnas.2026818118 . PMC 8126859. PMID  33947820 . 
  17. ^ Кардона, Р.; Миранда, Э.; Перальта-Салас, Д. (2023). «Вычислимость и поля Бельтрами в евклидовом пространстве». Журнал Mathématiques Pures et Appliquées . 169 : 50-81. arXiv : 2111.03559 . дои : 10.1016/j.matpur.2022.11.007.

Библиография

  • Брукшир, Дж. Гленн (1989). Теория вычислений: формальные языки, автоматы и сложность . Редвуд-Сити, Калифорния: Benjamin/Cummings Publishing Company, Inc.Приложение C включает в себя невозможность алгоритмов определить, содержит ли грамматика неоднозначности, и невозможность проверки правильности программы с помощью алгоритма в качестве примера проблемы остановки.
  • Халава, Веса (1997). Разрешимые и неразрешимые проблемы в теории матриц (технический отчет TUCS). Том 127. Центр компьютерных наук Турку. CiteSeerX  10.1.1.31.5792 .
  • Moret, BME; HD Shapiro (1991). Алгоритмы от P до NP, том 1 - Проектирование и эффективность . Редвуд-Сити, Калифорния: Benjamin/Cummings Publishing Company, Inc.Обсуждает неразрешимость проблем с помощью алгоритмов, имеющих экспоненциальную производительность, в главе 2 «Математические методы анализа алгоритмов».
  • Вайнбергер, Шмуэль (2005). Компьютеры, жесткость и модули . Принстон, Нью-Джерси: Princeton University Press.Обсуждается неразрешимость проблемы тождества для групп и различных проблем топологии.

Дальнейшее чтение

  • Пунен, Бьорн (2 апреля 2012 г.). «Неразрешимые проблемы: сэмплер». arXiv : 1204.0299 [math.LO].
Взято с "https://en.wikipedia.org/w/index.php?title=Список_неразрешимых_проблем&oldid=1250905939"