о вычислимости

[avva]

(понятно будет только компьютерщикам)

"Что будет, если вы найдете алгоритм в RP для решения SAT, со степенью многочлена, примерно равной 2^2^1000?"

Comments

[ygam.livejournal.com]

Следующие поколения математиков будут постепенно снижать этот коэффициент.

Пару лет назад открыли алгоритм умножения целых чисел быстрее алгоритма, основанного на FFT.

[(Anonymous)]

а можно ссылочку?

[ygam.livejournal.com]

http://www.cse.psu.edu/~furer/Papers/mult.pdf

[anril.livejournal.com]

шикарно!

[spamsink.livejournal.com]

The asymptotic improvement from
O(n log n log log n) to n log n 2^O(log* n)
might suggest that an actual speed-up only shows up for astronomically large numbers.

Как говорила одна старуха, много ли в корыте корысти?

[anonymous8216.livejournal.com]

Graham's number?

[anatoly borodin (from livejournal.com)]

Это которое, как в том анекдоте: "Идите по шпалам и считайте, и когда будет "а ну его нафиг!" - это только половина"?

Хорошее, годное число.

[flaass.livejournal.com]

И изо всех сил будут искать алгоритм в P. Найдут какие-нибудь индусы, со степенью 2^2^1001.

Но увы, все это пустые мечты...

[illy-drinker.livejournal.com]

Интересные ситуации с коэффициентами возникают когда у задачи два параметра - нормальные входные данные и "параметр" (обычно такими задачами занимается "parametric complexity" ) и константа решения задачи расмотренной с одним параметром есть функция от второго параметра
Например, задача проверки истина ли MSO (Monadic Second Order) формула на графе при условии, что treewidth у графа ограничена константой - линейная задача по размеру графа. Мешает только константа которая зависит от размера формулы; а константа - супер-потенциальная функция по размеру формулы.

[illy-drinker.livejournal.com]

P.S. Я имел ввиду, что нижний предел на константу суперэкспотенциален