Какая самая старая открытая проблема в TCS?

36

Эта проблема вдохновлена этим вопросом МО , который мне показался очень интересным.

Какая самая старая открытая проблема в TCS?

Очевидно, что этот вопрос нуждается в уточнении.

Во-первых, что такое TCS? Я думаю, что существование нечетных совершенных чисел не TCS. Я бы сказал, что десятой проблемой Гильберта является TCS. Я думаю, что такие проблемы, как «Можем ли мы построить X с помощью линейки и компаса», также являются TCS, поскольку они запрашивают алгоритм в ограниченной модели вычислений. Не может быть точного способа определить, в чем заключается проблема TCS, но используйте свое суждение. Возможно, один из тестов звучит так: «Если это будет решено, появится ли оно, скорее всего, в STOC / FOCS? Будет ли исследователь, решивший его, скорее всего, теоретиком-информатиком?

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

В-третьих, что такое «открытая проблема»? Под «открытой проблемой» я подразумеваю проблему, которая определенно считалась открытой когда-то. Возможно, оно появилось в конце статьи в разделе открытых проблем, или, может быть, есть свидетельства того, что некоторые люди работали над этим и потерпели неудачу, или, возможно, в литературе есть неверные доказательства, которые предполагают, что они были изучены. Пример чего-то, что не соответствует этим критериям: «Греки изучали объекты X и Y. Z явно является промежуточным объектом, наверняка им было интересно, можно ли его построить». Если нет литературы по Z с этого периода времени, то это не является открытой проблемой с того периода времени.

В-четвертых, что я имею в виду под «проблемой»? Я имею в виду конкретный вопрос «да / нет», а не что-то вроде «охарактеризовать все объекты X со свойством Y», потому что на такие вопросы часто нет удовлетворительного ответа. Довольно часто будут разногласия относительно того, был ли решен вопрос. Давайте не будем вдаваться в такие вопросы здесь. Если это не вопрос да / нет, но ясно, что он действительно открыт, это тоже хорошо. (В случае, если это не ясно, под «проблемой» я имею в виду формально заявленную проблему. Пожалуйста, не превращайте некоторые народные легенды об азартных играх в 16-м веке в вопрос о БПП и PSPACE.)

Наконец, поскольку это не большой вопрос, отправляйте ответ только в том случае, если вы считаете, что он старше, чем уже опубликованные ответы (или если вы считаете, что опубликованные ответы не удовлетворяют каким-либо другим условиям - например, они не являются TCS, или они не открыты). Это не беспорядочная коллекция старых открытых проблем.

Робин Котари
источник
13
"Какой лучший способ приготовить мясо?" В соответствии с моделью расчета у костра, каков наилучший алгоритм приготовления пищи? - актуально много тысяч лет назад, актуально и сейчас! Плюс есть много литературы по этой проблеме! (Извините, я не удержался ;-))
Даниэль Апон
3
Есть ли бог? Может быть проблема TCS, если это может быть решено компьютерами.
Сариэль Хар-Пелед
9
@ Дэниел, «Какой лучший способ разрезать торт» - это актуальный вопрос TCS !!!
Суреш Венкат
3
#offtopic: приятно видеть, что у переохлаждения теперь есть имя :)
Suresh Venkat
5
Я нашел книгу под названием «История алгоритмов: от гальки до микрочипа» ( amazon.com/dp/3540633693 ). Это может быть полезно при поиске достойной истории по (новым и старым) алгоритмам.
MS Dousti

Ответы:

38

Какова вычислительная сложность целочисленного умножения? Возможно, этот вопрос восходит, по крайней мере, к алгоритму «дупликации и посредничества» для целочисленного умножения, описанному в Rhind Mat математическом папирусе, который был написан около 1650 г. до н.э. , но претендует на то, чтобы быть копией значительно более старого документа.

Следует признать, что папирус Rhind явно не рассматривал сложность алгоритма. Так что, возможно, лучший ответ: какова сложность решения систем линейных уравнений? Исследование эффективных алгоритмов решения линейных систем восходит, по крайней мере, к комментарию Лю Хуэй, опубликованному в 263 году нашей эры , к Девяти главам математического искусства . В частности, Лю Хуэй сравнивает два варианта того, что в настоящее время распознается как исключение Гаусса, и подсчитывает количество арифметических операций, используемых каждой, с явной целью найти более эффективный метод.

Оба эти вопроса по-прежнему являются предметом активных исследований.

Jeffε
источник
9
В отличие от Робина, я не думаю, что разумно настаивать на том, чтобы вопрос был поставлен в его современной форме. Это все равно что держать исторические доказательства в соответствии с современными стандартами строгости. По этому стандарту аксиоматическая геометрия началась с Кляйна, а Евклид был просто греческим чуваком, который махал рукой.
Джефф
6
«По современным стандартам строгости, Евклид был просто каким-то греческим чуваком»: это мой следующий .sig :)
Суреш Венкат
2
Я думаю, что такие примеры в порядке. Чего я хотел избежать, так это того, что произошло при математическом переполнении. Был спор о том, рассматривали ли греки какую-то проблему только потому, что они изучали какую-то связанную проблему. Другой вещью, которую я хочу избежать, являются философские вопросы, такие как «Является ли детерминистическая вселенная» превращением в проблему P против BPP. Вы задали конкретную проблему, которую люди, которые ее поставили, считали вычислительной, и это вполне приемлемо.
Робин Котари
Этот вопрос был частично решен для целочисленного умножения в Интернете. arxiv.org/abs/1101.0768
Феликс
23

Поиски эффективного алгоритма факторинга, по-видимому, датируются, по крайней мере, Гауссом. Статья 329 Гаусса Disquitiones Arithmeticae (1801) имела следующую цитату ( источник ):

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length. ... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.

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

Арнаб
источник
2
Очень хорошая цитата. Здорово, как Гауссу было ясно, что современные алгоритмы факторинга были «трудоемкими и изобильными»!
Робин Котари
10

Следующее, цитата из

  • Goldwasser, S. and Micali, S. 1982. Вероятностное шифрование и как играть в ментальный покер, сохраняя в секрете всю частичную информацию. В материалах четырнадцатого ежегодного симпозиума ACM по теории вычислений (Сан-Франциско, Калифорния, США, 05–07 мая 1982 г.). STOC '82. ACM, Нью-Йорк, Нью-Йорк, 365-377. DOI = http://doi.acm.org/10.1145/800070.802212

Относится к другой проблеме, относящейся к Gauss 'Disquitiones Arithmeticae (1801):

(qN)=1(qN)

PS: К настоящему времени мы знаем две из четырех алгоритмических проблем :

  1. Факторинг (как упомянуто Арнаб);
  2. Определение квадратичной остаточности.

Какие еще две проблемы описаны Гауссом?

М.С. Дусти
источник
9

В литературе нашей страны есть поговорка, которую я буквально перевожу как «Загадка становится легче, когда ее разрешают». Хотя это не очень хороший перевод, это относится к тому факту, что когда у вас есть решение, вы можете легко его проверить; но до этого загадка кажется очень сложной.

Это относится к известной в настоящее время проблеме «FP vs. FNP»: если FNP = FP, проверка ответа на загадку так же проста, как и ее поиск. Однако если FNP N FP, то существуют «загадки», для которых найти решение гораздо сложнее, чем проверить решение.

Я полагаю, что эта проблема - самая старая открытая проблема TCS, но ее строгая формулировка восходит примерно 30 лет назад!

There seems to be a similar (yet somehow different!) proverb in the English language: "It's easy to be wise after the event" or "It's easy to be smart after the fact."

РЕДАКТИРОВАТЬ: «Можем ли мы вычислить числа в поли-времени» является еще одной открытой проблемой TCS, но я думаю, что она моложе, чем проблема, упомянутая выше.

Вот два списка открытых проблем TCS в сети:

У нас также есть такой список здесь, на CSTheory.

М.С. Дусти
источник
1
Поскольку я ограничиваю это строгими формулировками задач, я бы предположил, что вопрос о факторинге и FP = FNP может быть формализован только тогда, когда у нас есть машины Тьюринга, полиномиальное время и т. Д.
Робин Котари
@ Робин: Вы можете не спрашивать о старых, формализованных открытых проблемах TCS, если в старости не было даже компьютеров! :)
MS Dousti
1
@ Садек: Я не против, если самый старый вопрос окажется вопросом, заданным в 1922 году. Я настаиваю на строго заданных вопросах, потому что в противном случае люди будут цитировать 4000-летние тексты, утверждающие, что какое-то предложение о вселенной было вычислительным вопросом замаскированный
Робин Котари
В каком году была сформулирована эта проблема?
Дэйв Кларк
3
@Sadeq: Да, но это не вопрос P против NP, если кто-то не формализует модель и т. Д. Я имею в виду, что он мог бы с тем же успехом представлять некоторый другой вопрос (скажем, L против NL, или P / poly против NP / poly, или какой-то вопрос в другое поле). Во-вторых, это широко распространенное убеждение, а не то, что считается открытой проблемой. Это не то, что требует доказательств в своей первоначальной формулировке: это просто наблюдение о жизни.
Робин Котари
3

Я подвергаю сомнению вашу исключающую теорию чисел, включающую вопросы о том, являются ли некоторые теории чисел конечными или бесконечными как часть TCS и определенно утверждают иначе. Греки спросили:

  • есть ли какие-то странные идеальные числа? [возможно, рассматривается Евклидом]

  • Есть ли бесконечное число двойных простых чисел?

TMxTMy

возможно, это две древние алгоритмические проблемы, и греки первыми разработали TCS, главным образом, в форме теории чисел, а ранние проблемы теории чисел - это просто частные случаи проблемы остановки Туринга и ранние косвенные доказательства ее сложности. и существует тесная связь между вопросом / поиском / поиском доказательств и теорией неразрешимости.

возможно новое исследование показывает, что гипотеза Коллатца, когда-то считавшаяся любопытством теории чисел, имеет глубокие связи с теорией вычислимости и может лежать прямо на границе между неразрешимыми и разрешимыми проблемами. также приведенный вами пример 10-й проблемы Гилберта показывает очень фундаментальную связь между теорией чисел и TCS.

два других древних алгоритмических вопроса:

  • Что является эффективным или наиболее эффективным алгоритмом для вычисления gcd, наибольший общий делитель?

  • Что такое эффективный или наиболее эффективный алгоритм для вычисления простых чисел?

согласился, что второй вопрос довольно тесно связан с факторингом, но, конечно, не совсем так. он был рассмотрен сито и евклидом Эратосфена. конечно, недавно было показано, что AKS использует P, но даже тогда алгоритм не является полностью оптимальным.

существует очень современное исследование TCS по алгоритму euclids gcd (т. е. 20 век), которое показало, что числа Фибоначчи дают ему наихудшую производительность. [не уверен, кто первый показал это]

пока алгоритм Евклида не окажется оптимальным, возможно, эффективное вычисление gcd все еще остается открытым.

ВЗН
источник
7
я не согласен с большинством из того, что вы говорите (тот факт, что вы можете создавать все виды машин Тьюринга, которые останавливаются, если существуют некоторые предполагаемые объекты, не делает эти проблемы существования проблемой вычислимости). но в конце у вас есть хорошая мысль: детерминистическая генерация простого числа в некотором диапазоне является разумной современной версией старого квеста по поиску «формулы для простых чисел». Я бы поддержал вас, если бы вы написали сфокусированный ответ по этим направлениям
Сашо Николов
1
Я согласен с приведенным выше комментарием: гипотеза Пуанкаре может быть сформулирована как проблема остановки и для машин Тьюринга, но не было достигнуто никакого прогресса с использованием методов, специально разработанных сообществом CS. То же самое можно сказать и о таких теоретических задачах с числами, которые могут быть важны в вычислительном отношении.
Коди
2

Не уверен, насколько серьезен этот ответ, но ....

Это действительно зависит от того, насколько широко вы хотите определить свой вопрос.

Конечно, "можно ли построить интеллектуальную машину?" это самый старый открытый вопрос в CS, который начал информатику, но, вероятно, старше на миллиниум или два, чем CS. Нет? (Это вопрос теории, поскольку он требует ответа, а не самой машины ...)

Естественной ссылкой на поиск интеллектуальной машины был бы Голем ... http://en.wikipedia.org/wiki/Golem#History

Сариэль Хар-Пелед
источник
0

Я могу ответить на ваш вопрос со 100% уверенностью в течение определенного периода времени. Если мы рассмотрим период от оригинальной статьи Хартманиса и Стернса до какого-либо момента в будущем, самая старая проблема в TCS, которая до сих пор остается открытой:

Каковы минимальные накладные расходы, необходимые для моделирования детерминированных ТМ?

T2(n)T(n)logT(n)

logT(n)

chazisop
источник
1
logT(n)
1
PNP
1
Это могло бы использовать некоторые пояснения для тех, кто не знает эти документы подробно: какой тип ТМ моделируется? Какой тип машины выполняет симуляцию?
Funkstar
Я не верю, что разъяснение необходимо. То, что в первой статье используется модель Multitape TM, является общеизвестным фактом, поскольку она содержит некоторые основные определения TCS, а также явно упоминается в заголовке статьи Hennie and Stearns.
chazisop
1
На мой взгляд, ваша формулировка открытого вопроса все еще слишком расплывчата. Несмотря на то, что это хорошо известно в ToC сообщества, Хартманис, Хенни и Stearns работа с многоленточных ДЧ, что просто делает ваш ответ бесполезен тем , во многих других областях ТКС. Вы должны рассмотреть хотя бы добавление в вопрос квалификатора «multitape». (И даже тогда у вас есть проблема в том, что в симуляции Хартманиса и Стернса используется ТМ с 1 лентой, в то время как в симуляции Хенни и Стернса используется ТМ с 2
лентами