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

[avva]

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

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

Comments

[illy-drinker.livejournal.com]

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

[illy-drinker.livejournal.com]

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