Жесткие нижние оценки теоремы Савича

Прежде всего, заранее прошу прощения за любую глупость. Я ни в коем случае не эксперт по теории сложности (отнюдь! Я студент, берущий свой первый класс по теории сложности). Вот мой вопрос. Теперь теорема Савича гласит, что Теперь мне интересно, если эта нижняя граница была жесткой, то есть это что-то вроде строки недостижимо. NSPACE ( f ( n ) ) ⊆ DSPACE ( ( f ( n ) ) 1.9

Кажется, что здесь должен быть прямой комбинаторный аргумент - каждый узел в графе конфигурации для детерминированной машины Тьюринга имеет только один исходящий ребро, в то время как каждый узел в графе конфигурации недетерминированной машины Тьюринга может иметь больше чем один исходящий край. Алгоритм Савича заключается в преобразовании графов конфигурации с любым исходящим ребром в графы конфигурации с исходящими ребрами.$<2$

Поскольку граф конфигурации определяет уникальную TM (не уверен в этом), комбинаторный размер последнего почти наверняка больше, чем первый. Эта «разница», возможно, является фактором , а может быть и меньше - я не знаю. Конечно, есть много маленьких технических проблем, которые нужно решить, например, как вам нужно убедиться, что нет петель и т. Д., Но мой вопрос, если это разумный способ начать доказывать что-то подобное. $n^2$

Это хорошо известный открытый вопрос. В теории сложности вы увидите много открытых вопросов, по которым вы удивитесь, почему никому не удалось их решить. Частично причина в том, что нам нужны новые люди, как вы, чтобы помочь нам решить их :)

Чтобы получить последний результат в этой области, показывающий, что алгоритм Савича является оптимальным в некоторой ограниченной модели, см . Статью Аарона Потечина FOCS .

В частности, он начинает с приятного наблюдения, что, поскольку граф конфигурации детерминированной TM имеет только одно исходящее ребро (после фиксации ввода), можно думать о нем как о неориентированном графе, и поэтому вопрос становится примерно таким: ориентированный граф из вершин с двумя специальными вершинами , если мы сопоставим его с вершинным неориентированным графом (также со специальными вершинами ), так что существование каждого ребра в зависит от одно ребро в и есть путь от до в если есть путь междуn s , t N G ′ s ′ , t ′ G ′ G s t G s ′ t ′ G ′ N $G$$n$$s,t$$N$$G'$$s',t'$$G'$$G$$s$$t$$G$$s'$ и в , насколько больше должно быть от .$t'$$G'$$N$$n$

Чтобы показать, что алгоритм Савича является оптимальным, нужно показать, что должно быть не менее . Чтобы показать , достаточно показать более слабую оценку, что для любой константы . Я почти уверен, что даже неизвестно, хотя, возможно, что-то вроде известно по некоторым не столь интересным причинам.2 Ω ( log 2 n ) = n Ω ( log n ) L ≠ N L N > n c c N > n 10 N ≥ n $N$$2^{\Omega(\log^2 n)} = n^{\Omega(\log n)}$$L\neq NL$$N > n^c$$c$$N > n^{10}$$N \geq n^2$

Я думаю, что мы не знаем, является ли это жестким. Иначе мы бы знали, что .$L \neq NL$