После обсуждения нижних границ для 3SAT [ 1 ] мне интересно, каковы основные результаты нижней границы, сформулированные как компромиссы пространства-времени. Я исключаю такие результаты, как, например, теорема Савича; хорошая статья будет сосредоточена на одной проблеме и ее границах. Примером может быть:
«Пусть T и S - границы времени и пространства любого алгоритма SAT. Тогда мы должны иметь T⋅S≥n2cos (π / 7) −o (1) бесконечно часто». (Данный в [ 1 ] Райан Уильямс.)
или
«SAT не может быть решена одновременно за n 1 + 0 (1) времени и n 1-ε пространства для любого ε> 0 на общих недетерминированных машинах Тьюринга с произвольным доступом». (Лэнс Фортноу в 10.1109 / CCC.1997.612300)
Кроме того, я включаю определения естественных пространственно-временных классов сложности компромисса (исключая классы схем).
источник
Ответы:
Вот несколько дополнительных ссылок. Больше можно найти, посмотрев на документы, которые цитируют их.
источник