о смене перспективы

[avva]

Я с детства - из гарднеровских книжек, наверняка - помню прекрасный рассказ о математике-герое, который разложил на множители число 2⁶⁷-1, что до него никому не удавалось сделать. Он пришел на заседание математического общества, подошел к доске, написал на одной половине доски вычисление 67-й степени двойки минус один, потом перешел на другую половину, написал два больших числа, умножил их в столбик, получил тот же ответ, и сел на место, не произнеся за все это время ни слова. За что и был удостоен овации; а потом сказал якобы, в ответ на вопрос, сколько времени он затратил на то, чтобы найти множители: "все воскресенья за три года".

С детства помню, как меня эта история впечатлила и как я восхищался им; и вот почему-то сегодня вспомнил и подумал, какой бред, зачем он убил на это столько времени, и чем тут восхищаться? Ясно, что сейчас компьютер это находит за долю секунды; но и тогда никому не нужно было это знать ни для чего. Более того, я поискал описание этого случая и обнаружил, что оказывается уже было известно, что 2⁶⁷-1 не простое число, не знали только множители! (в детстве я этого точно не знал, думал, что он опроверг гипотезу, что оно простое). Это тем более, еще многажды делает всю эту работу бессмысленной.

Ну действительно же фигня какая-то полная.

Comments

[adp.myopenid.com (from livejournal.com)]

Ну это да. Но пользы от решения 3n+1 тоже не знаю.

А вот вопрос о разнице задач распознавания и вычисления очень даже.
1. Например, можно за полиномиальное время можно проверить число на простоту (без подвоха, детерминированным алгоритмом, степень полинома не выше шестой), а вот находить простой делитель за такое же время не умеют. Полиномиальная иерархия частично строится как раз на таких задачах, NP - типичный пример.
2. В конструктивной логике, где нет правила двойного отрицания, можно доказать практически все те же теоремы, которые мы знаем. Только доказательства оказываются длиннющими при замене некоторых шагов "от противного" на явное построение.

Так что работа, я считаю, непустая :-) Может, его ход мыслей можно применить для создания эффективного эвристика для факторизации?

[avva.livejournal.com]

Да мы даже и не знаем ход его мыслей :)

[adp.myopenid.com (from livejournal.com)]

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