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

[avva]

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

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

Comments

[arcbishop.livejournal.com]

там где-то еще n должно быть, я так думаю.

[salas.livejournal.com]

n — аргумент этого самого многочлена.

[arcbishop.livejournal.com]

ой, торможу. сорьки.

[kot-begemot.livejournal.com]

У каждого поколения - свои извращения. Пятьдесят лет назад было модно доказывать Великую Теорему Ферма, сто лет назад - строить вечные двигатели, ещё раньше - искать квадратуру круга, метод удвоения куба или трисекции угла.
Теперь вот в моду вошли NP-полные задачи.

[a-konst.livejournal.com]

Увы, искать квадратуру круга, строить вечные двигатели и даже доказывать последнюю теорему Ферма модно и сейчас.

[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. Я имел ввиду, что нижний предел на константу суперэкспотенциален

[lxe]

^ - это побитовое исключающее "или"? =)

[avva.livejournal.com]

Возведение в степень.

[eterevsky.livejournal.com]

Через пять лет степень улучшат до 2^2^30, ещё через десять до 2^100, а там, глядишь им и пользоваться станет возможно. :-)

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

[alaev.livejournal.com]

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

После этого появится шанс, что количество перейдёт в качество.

[ygam.livejournal.com]

http://en.wikipedia.org/wiki/AKS_primality_test

In 2005, Carl Pomerance and H. W. Lenstra, Jr. demonstrated a variant of AKS that runs in O(log^6+ε n) operations where n is the number to be tested, a marked improvement over the initial O(log^12+ε n) bound in the original algorithm [2].

[eterevsky.livejournal.com]

Спасибо! Я помнил, что детерминированные тесты на простоту имеют показатель в районе семи, но запамятовал, что в первоначальном варианте было 12.