Есть ли проблемы, требующие более чем двукратного экспоненциального времени?

Question

Есть ли проблемы, требующие более чем двукратного экспоненциального времени?

Есть ли проблемы, для которых все известные алгоритмы требуют более чем двукратного экспоненциального времени?

1

time-complexity complexity-theory exponential

Источник

user2992539 24 мар '14 в 18:42

1 ответ

Решение

Другие вопросы по тегам time-complexity complexity-theory exponential

user501557 24 мар '14 в 19:01 2014-03-24 19:01 · Accepted Answer · 2014-03-24 19:01

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

При условии, что машина Тьюринга M и строка x принимают M в течение 2^{2^2ⁿ} шагов?

Эта проблема доказуемо не может быть решена ТМ менее чем за 2^{2^2ⁿ} шагов, и, так как ТМ может моделировать компьютер только с замедлением n⁶, это означает, что ни один компьютер не может решить эту проблему за время o (2^{2^2ⁿ}),

Конечно, это не очень интересная проблема (я не понимаю, почему вы хотите решить эту проблему, кроме как в очень надуманных ситуациях), но известно, что для решения этой проблемы требуется три экспоненциальных времени.

Надеюсь это поможет!