Пространственно-временной компромисс нижних границ

13

После обсуждения нижних границ для 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)

Кроме того, я включаю определения естественных пространственно-временных классов сложности компромисса (исключая классы схем).

Michaël Cadilhac
источник
1
хмм. Еще один пример того, как не нужен тег CW.
Суреш Венкат
Что вы имеете в виду?
Микаэль Кадилхак
1
Суреш говорит, что вам не нужно ставить «вики сообщества» на этот вопрос, если вы перефразируете вопрос, чтобы он был чем-то другим, а не большим списком, и вы более конкретно указали, что вы ищете. Кроме того, это действительно "мягкий вопрос"?
Райан Уильямс
Ну, я хочу большой список, и вопрос, не будучи конкретным, я думаю, является хорошим способом получить его. Этот вид списка запрещен? (Я могу в значительной степени сделать вывод, что я сделал что-то не так, поскольку ответа не было дано, но не знаю, что.) Кроме того, это мягкий вопрос, поскольку он не требует какой-либо интеллектуальной работы.
Михаэль Кадилхак
2
Мы надеемся прояснить это в конце концов в FAQ. Я бы сказал, что это не мягкий вопрос, потому что он технический. Мягкий вопрос - больше о темах, связанных с исследованиями - куда идти в аспирантуру, как читать газеты и т. Д.
Суреш Венкат

Ответы:

12

Вот несколько дополнительных ссылок. Больше можно найти, посмотрев на документы, которые цитируют их.

пT2SΩ(N3) проблемы отличимости элементов .

О(N)О(1)К+1TSΩ(N2)К

Sо(N)Tω(N)

TSΩ(N2) справедливо для многолентовых машин Тьюринга, решающих SAT, опираясь на аналогичную нижнюю оценку Кобэма для PALINDROMES.

Райан Уильямс
источник