Теория структурной сложности
Мы знаем, что L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} и что L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , где L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Мы также знаем , что...
Многие важные результаты в теории вычислительной сложности и, в частности, в теории «структурной» сложности, обладают интересным свойством, которое можно понять как фундаментально следующее (как я вижу это ...) из алгоритмических результатов, дающих эффективный алгоритм или протокол связи для...
задира Поскольку проблема длинная, здесь есть особый случай, который отражает ее суть. Проблема: Пусть A - детриминистический алгоритм для 3-SAT. Является ли проблема полного моделирования алгоритма A (на каждом экземпляре задачи). P-Space сложно? (Точнее, есть ли основания полагать, что эта задача...
Фон Известно , что существует оракул такое , что .P S P A C E A ≠ P H AAAAPSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A Даже известно, что разделение справедливо относительно случайного оракула. Неофициально можно интерпретировать это как означающее, что существует много оракулов, для которых и...
Не известно , если изоморфизм графов (GI) для сильно регулярных графов (SRGS) в P . Есть ли намеки на то, что это может или не может быть GI- Complete? Есть ли сильные последствия в таких случаях? (Аналогично убеждению, что GI не может быть...
В нашей недавней работе мы решили вычислительную проблему, возникшую в комбинаторном контексте, исходя из предположения, что , где - это -версия . Единственной найденной нами статьей о была статья Бейгеля-Бурмана-Фортнау 1998 года , в которой упоминается комплексный зоопарк . Мы понимаем, что можем...
Две статьи, которые я бы включил: Д. Козен, "Индексация субрекурсивных классов" , STOC, 1978. Р. Лэднер, "О структуре полиномиальной временной сводимости" , JACM, 1975....
Для любого произвольного NP-полного языка всегда ли найдется надмножество множителей, дополнение которого также бесконечно? На /cs//q/50123/42961 была запрошена тривиальная версия, в которой суперсет не должен иметь бесконечного дополнения. Для целей этого вопроса можно предположить, что . Как...
Имеет ли означают E = N E
Пусть ATISP(f(n),g(n))ATISP(f(n),g(n))\mathsf{ATISP}(f(n), g(n)) будет классом языков, определяемым чередующимися машинами Тьюринга, которые останавливаются во времени f(n)f(n)f(n) используя пространство g(n)g(n)g(n) . Пусть A A L T S P (F( н ) , г( н ) )AALTSP(f(n),g(n))\mathsf{AALTSP}(f(n), g(n))...