Простая проблема, разрешимость которой неизвестна

92

Я готовлюсь к выступлению, направленному на студентов по математике, и в рамках этого я рассматриваю возможность обсуждения концепции разрешимости. Я хочу привести пример проблемы, о которой мы пока не знаем, что она разрешима или неразрешима. Таких проблем много, но пока что ни одна из них не является хорошим примером.

Что такое простая для описания проблема, разрешимость которой открыта?

Лев Рейзин
источник
26
Задача Коллатца - это простая для описания задача, разрешимость которой открыта. Было показано, что обобщение проблемы Коллатца неразрешимо. math.mit.edu/~poonen/papers/sampler.pdf mathworld.wolfram.com/CollatzProblem.html
Мухаммед Аль-Тюркистани,
2
Возможно, вы также можете показать этот хороший «трюк»: напишите небольшую программу (вы можете назвать ее «goldbach»), которая перебирает четные целые числа и проверяет, что n i = p j + p k для некоторых простых чисел p j , p k < n i и останавливается в отрицательном случае ... затем скажите «ну, мы не знаем, разрешима ли проблема остановки для этой программы!» :-). Это показывает сильную корреляцию между проблемами теории чисел и проблемой остановки. ni5ni=pj+pkpj,pk<ni
Марцио Де Биаси
8
Это кажется хорошим, но концепция разрешимости не применима только к одному конкретному случаю, поскольку в обоих случаях ответом является просто фиксированное «да / нет».
Лев Рейзин
6
@MarzioDeBiasi, это не «сильная корреляция» между проблемой остановки и теорией чисел. Любую гипотезу вида «ломкие виджеты существуют / не существуют» можно превратить в программу, которая останавливает работу, если есть ломкий виджет, если разрешимость разрешима, а виджеты рекурсивно перечислимы. Существование такой программы - только самая тривиальная связь между проблемой остановки и теорией виджетов.
Дэвид Ричерби
2
@DavidRicherby: довольно убедительно :-). Я только пытался выявить тот факт (удивительно для меня), что решение проблемы остановки для нескольких кусков кода соответствует решению давней математической гипотезы. Поэтому я должен заменить «сильная корреляция» на «слабая корреляция, но удивительно для меня» :-) :-)
Марцио Де Биаси

Ответы:

91

Матрица смертности Задача для матриц 2х2. Т.е., учитывая конечный список из 2x2 целочисленных матриц M 1 , ..., M k , можно ли умножить M i в любом порядке (с произвольным количеством повторений), чтобы получить матрицу из всех 0?

(Известно, что случай 3х3 неразрешим. Случай 1х1, конечно, разрешим.)

Скотт Ааронсон
источник
6
epubs.siam.org/doi/abs/10.1137/1.9781611974782.12 Игорь Потапов и Павел Семухин недавно показали, что это можно решить.
Чао Сюй
4
@ChaoXu: Кажется, эта статья предназначена только для неособых матриц.
2
@RickyDemer Вы правы, моя ошибка.
Чао Сюй
57

ОБНОВЛЕНИЕ: проблема, которую я упомянул здесь, теперь, как известно, неразрешима! http://arxiv.org/abs/1605.05274 Более того, статья вдохновлялась чтением именно этого ответа. :)


Программисты из вашей аудитории по математике могут быть удивлены, узнав, что вопрос "является ли этот тип неявно конвертируемым в этот тип?" Не известно, чтобы быть разрешимым в любой из Java 5, C # 4 и Scala 2.

Для получения более подробной информации см. Статью Эндрю Кеннеди и Бенджамина Пирса «О разрешимости номинального подтипа с дисперсией» . В статье приводятся некоторые примеры дополнительных ограничений для систем типов этих языков, при которых номинальный подтип становится известным как разрешимый или известный как неразрешимый.

Интересно, что статья была написана задолго до того, как в C # были добавлены общая ковариация и контравариантность, но авторы правильно предвидели направление, в котором движется язык. (Это неудивительно; авторы разработали базовую поддержку дисперсии в CLR, которой я воспользовался, добавив дисперсию в C #! Они сделали тяжелую работу.)

Эрик Липперт
источник
7
@vzn: компилятор Microsoft C # может быть использован для неограниченной рекурсии. См. Мою статью на эту тему: blogs.msdn.com/b/ericlippert/archive/2008/05/07/…
Эрик Липперт
3
@vzn: есть способы заставить компилятор Java вести себя плохо, но я не знаю деталей.
Эрик Липперт
2
@vzn Язык типов Scala завершен по Тьюрингу, и, следовательно, проверка типов в Scala может выполнять цикл. Смотрите здесь для деталей. То же самое относится и к Haskell . Я недостаточно знаком с C # и Java, чтобы знать, можно ли заставить их соответствующие средства проверки типов зацикливаться.
Мартин Бергер
3
@vzn: Также это может вас заинтересовать: разрешение перегрузки в C # 3 является как минимум NP-HARD, потому что вы можете заставить компилятор решать произвольные проблемы SAT: blogs.msdn.com/b/ericlippert/archive/2007/03 / 28 /…
Эрик Липперт
7
@vzn: Наконец, вопрос "это несколько академично?" конечно ответили да. Вопрос "бла, как известно, разрешим?" по своей природе является академическим вопросом. Эти случаи не возникают в реалистичном бизнес-коде. Важность этого вопроса с инженерной точки зрения заключается в безопасности ; Может ли враждебная третья сторона предоставить код, анализ которого перед запуском может привести к плохому поведению? Это та ситуация, в которой мы находимся в Интернете, когда враждебные третьи стороны отправляют JavaScript в ваш браузер.
Эрик Липперт
47

Десятая проблема Гильберта о рациональных числах: «Есть ли у этого полиномиального уравнения рациональное решение?»

Борис Бух
источник
1
Спасибо. У вас есть ссылка на то, что она открыта?
Лев Рейзин
1
См. Www-math.mit.edu/~poonen/papers/subrings.pdf (второй абзац). Есть также пояснительная статья на www-math.mit.edu/~poonen/papers/aws2003.pdf
Борис Бух,
было бы также полезно увидеть набросок / описание того, почему эта проблема не эквивалентна 10-й задаче Гильбертса и это же доказательство не применимо.
2013 года
2
vzn: уравнения над рациональными числами можно рассматривать как частный случай уравнений над целыми числами (умножением для очистки знаменателей). Таким образом, вопрос заключается в том, является ли этот частный случай 10-й проблемы Гильберта уже неразрешимым. Диофантовы уравнения, полученные из существующих доказательств, не имеют специальной формы.
Скотт Ааронсон
1
@vzn Одна из причин, по которой это неуловимо, заключается в том, что большинство (возможно, все) стратегий доказательства нарушают гипотезу Мазура. Смотрите страницу 1 первой ссылки Бориса Буха для дополнительной информации.
Дэвид Э Шпейер
29

Проблема заданного линейного повторения вместе с его начальными значениями, принимает ли оно значение 0?

Две ссылки:

http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/

http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf

Магнус Найти
источник
3
Теперь в Википедии: en.wikipedia.org/wiki/Skolem_problem
Дэвид Эппштейн
23

Простая проблема, разрешимость которой неизвестна, заключается в следующем (я думаю, что она все еще открыта):

Бесконечные шахматы :

Входные данные : конечный список шахматных фигур и их начальных позиций на доске ; Вопрос : могут ли белые форсировать мат?Z×Z

Если мы добавим ограничение, согласно которому белые должны спариться за ходов ( n является частью входных данных), то это становится разрешимым: см. Дэн Брумлев, Джоэл Дэвид Хэмкинс и Филипп Шлихт. Проблема взаимных шахмат в бесконечных шахматах разрешима. ,nn


Другая простая проблема - поведение муравья Лэнгтона на конечной начальной конфигурации.

Поведение муравья Лэнгтона с конечной поддержкой :

Квадраты на плоскости окрашены в разные цвета: черный или белый. Мы произвольно определяем один квадрат как «муравей». Муравей может путешествовать в любом из четырех основных направлений на каждом шаге, который он предпринимает. Муравей движется по правилам ниже:

  • На белом квадрате поверните на 90 ° вправо, измените цвет квадрата, продвиньтесь на одну единицу
  • На черном квадрате поверните на 90 ° влево, измените цвет квадрата, продвиньтесь на одну единицу вперед

Вход : конечная конфигурация (черно-белая) плоскости и положения муравья;
Вопрос : муравей всегда заканчивает строительство повторяющейся бесконечной "магистрали"?

введите описание изображения здесь

Для бесконечной поддержки проблема неразрешима, см .: A. Gajardo, A. Moreira и E. Goles, Сложность муравья Лэнгтона

Марцио де Биаси
источник
20

Задача Коллатца - это простая для описания задача, разрешимость которой открыта. Это предполагает простое повторение элементарных арифметических операций.

n / 2 для четного целого числа, 3 n + 1 для нечетного целого числаf(n)={ n/23n+1

Проблема состоит в том, чтобы решить, всегда ли при повторении этой функции возвращаться к 1 для заданного натурального числа .n0

Интересно, что обобщение проблемы Коллатца оказалось неразрешимым.

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

1- Неразрешимые проблемы: образец, BJORN POONEN

2- Вайштайн, Эрик У. «Проблема Коллатца». Из MathWorld - веб-ресурс Wolfram.

3- Проблема 3X + 1: обзор , Джеффри С. Лагариас

Мухаммед Аль-Туркистани
источник
13
Строго говоря, ответом на ваш конкретный вопрос является просто «да» или «нет», поэтому он не может быть неразрешимым. С другой стороны, определение того, является ли конкретное число числом Коллатца, может быть неразрешимым.
Лев Рейзин
@LevReyzin Спасибо. Отредактировано, чтобы исправить проблему.
Мухаммед Аль-Туркистани,
рад, что этот ответ теперь включен, и предложить, чтобы все другие основные проблемы теории открытых чисел можно было сформулировать аналогично другим комментариям / ответам, и думаю, что эта фундаментальная связь близка к теореме о центральном мосте, не исследованной теоретическими сообществами.
vzn
изучение гипотезы Коллатца с более TCS / эмпирического угла со многими ссылками здесь (например, через рекурсию датчика FSM , систему меток и т. д.)
vzn
16

Разрешимость конъюнктивного удержания запросов открыта уже более двадцати лет. Решение этой проблемы станет прорывом в теории баз данных.

Q1Q2Q1IQ2I

В конъюнктивных запросах используется AND для связи экзистенциально количественных предикатов. В терминах SQL конъюнктивные запросы - это запросы SELECT-FROM-WHERE, использующие "=" и "AND", но без подзапросов или агрегации. Это, пожалуй, самый распространенный вид запросов к базе данных, и включает в себя большинство запросов поисковых систем.

IQ1Q2

(N,+,×)(N,+,×)

Для ознакомления с обширной литературой и строгим обращением, см. Статью ToDS (в печати) некоторых людей.

QRQQ AND RQ

Андраш Саламон
источник
Вот связанная статья .
Мартин Бергер
1
@MartinBerger: версия ToDS включает в себя упомянутое выше доказательство твердости NP, имеет полные доказательства и является открытым доступом (хотя и пропускает материал об объединениях CQ из-за недостатка места). dx.doi.org/10.1145/2556524
Саламон
15

Проблема корреспонденции с фиксированным числом плиток от 3 до 6.

Хотя это не совсем просто описать, у него есть очень «игривое» описание, и я считаю его подходящим для разговоров на уровне интуиции.

Shaull
источник
13

Обобщенная проблема высоты звезды: «Сколько вложений звезд Клини мне нужно, чтобы представить этот регулярный язык с регулярным выражением с дополняемым дополнением?»

Мы даже не знаем, верен ли алгоритм, который всегда возвращает 1 (кроме 0 для языков без звездочек, что является решаемым случаем).

Денис
источник
10

Задача из теории автоматов.

D

xDxxL(D)Primes

Комментарии: Первоначально я слышал эту проблему из ответа от Джеффри Шаллита об обмене стеками. Если вы знаете какие-либо ссылки на него, пожалуйста, дайте мне знать. Спасибо!

Похожие сообщения:

(1) Есть ли какие-либо открытые проблемы в отношении DFA?

(2) https://cs.stackexchange.com/questions/48084/determining-if-infinite-binary-language-dfas-contain-at-least-1-prime

Связанная работа: https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf

«Минимальные элементы для простых чисел» К. Брайта, Р. Девиллера и Дж. Шаллита

Майкл Вехар
источник
7

Итерированные карты на интервале (описание здесь ):

(очень связано с проблемой, предложенной Магнусом Финдом)

FxxxF(x)F(F(x))FxF

Fxyxy

F

FxyxF

Ссылка: Асарин 2011 .

Николас Перрен
источник
2

Кажется, есть довольно естественный способ / угол для изучения этого вопроса, который используется по крайней мере в 3 статьях следующим образом.

TM(k,l)klk,lk,l

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

поэтому, очевидно, существует явление, подобное «точке перехода», действующее здесь, но не в вычислимой области, а в необычном смысле между вычислимым и невычислимым.

ВЗН
источник
ps De Mol ref pdf не был загружен для меня из arxiv на момент написания статьи, он зависает
vzn
-3

28

Кроме того, в качестве примера «близкого промаха» или «открытого вопроса, который был решен относительно недавно после завершения ТМ», машина Wolfram 2,3 была признана универсальной в 2007 году за приз в 25 тысяч долларов . конкурс был объявлен в мае 2007 года, а конкурс был объявлен победителем Смитом в октябре 2007 года .

ВЗН
источник
-10

Существует довольно естественный способ сопоставить большинство открытых проблем с вопросами (не) разрешимости. как правило, не известно, что большинство открытых проблем доказуемо или недоказуемо.

в сети существует неформальное замешательство в отношении неразрешимости проблемы P vs NP , которая не является строго проблемой решения, поэтому говорить о ее неразрешимости технически некорректно. но, с другой стороны, между неразрешимостью и доказуемостью, похоже, существует тесная / естественная связь, как изложено ниже.

например рассмотреть

LxO(nx)

этот язык разрешим? это вопрос о языке с открытой разрешимостью, который в основном тесно (даже практически идентичен) проблеме P против NP и присущей ему (не?) доказуемости.

что касается P против NP как «простого для описания», то для этого требуются только понятия ТМ , система обозначений времени исполнения Big O , недетерминизм, которые являются довольно простыми (некоторые из самых основных понятий TCS) и преподаются на уровне бакалавриата или которые являются одаренными ученик средней школы мог понять.

на самом деле NP против P / Poly также открыта и может быть отображена на открытый вопрос о разрешимости таким же образом, и это можно сформулировать как довольно простую проблему о росте минимальных (монотонных?) схем, чтобы признать NP завершенным проблемы (например, клики).

ВЗН
источник
3
LxL=xΘ(nx)LL
2
говорить, что целое число не вычислимо, - это чепуха. и я не думаю, что принцип исключенного среднего зависит от того, доказуемо ли утверждение.
Сашо Николов
5
либо исправьте свой ответ, либо перестаньте оставлять комментарии. Я видел эти вопросы, но если вы не можете использовать их или ответы на них, чтобы исправить свой полный беспорядок в ответе, или, что еще хуже, если вы не хотите, возможно, вам следует обратиться к другому сообществу.
Сашо Николов
5
Кстати, проблема в вашем ответе тривиально разрешима, независимо от разрешения или формальной независимости проблемы P vs NP от ZFC. Кроме того, создание проблем, которые могут быть неразрешимыми или тривиально разрешимыми в зависимости от истинности известной гипотезы, является не чем иным, как милым упражнением (в котором вы до сих пор не справились), и в большинстве случаев ничего не показывает о внутренней сложности гипотезы. ,
Сашо Николов